Re: In-place algorithm

is this merge sort an in-place algorithm?

I am assuming you are taliking about arrays.
No. Auxilary memory is required.
Merge sort an be in-place but it is extremely difficult problem,
particularly if you want it to remain stable.
It usually costs O(N * log N * log N) in-place.
There has been some progress over the years but not to the extent that
inplace merge sort is as efficient as merge sort with auxilary memory.

If you are talking about linked lists, then the links themselves can be
manipulated, no auxilary memory is required.

Stephen Howe


.

Relevant Pages

  • Re: Help with Array(s)
    ... I would think XML would return in something with an XML schema and you could ... Array.Sort sorts one-dimentional arrays, but don't think it will 2dim arrays ... to sort list by second int value and display. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: does C# have any collection objects that support sort functionality so that I dont have to writ
    ... the IComparable interface. ... Also, since arrays are strongly typed, you know that all elements are of the ... for ArrayLists. ... The Sort() method will utilize each object's IComparable ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Arrays
    ... > Arrays are very rich objects in CL. ... > copying some sort of object, or testing one for equality, there are ... > The Lisp reader does a lot of this when reading strings and symbols. ...
    (comp.lang.lisp)
  • Re: IsAnagram
    ... Sort both words and compare both arrays. ... So I am looking for the most efficient algorithm. ... Sort both sounds like the most efficient. ... array first. ...
    (comp.lang.c)
  • Re: Generic In-Place Sort
    ... > There is a bug in that you get an Access Violation if you sort an empty ... So with an empty array, ... specializations for sorting arrays of Integers and arrays of strings. ...
    (comp.lang.pascal.delphi.misc)