Re: In-place algorithm

Juha Nieminen <nospam@xxxxxxxxxxxxxx> writes:

CBFalconer wrote:
Yes, singly-linked lists are easily merge-sorted. I posted the
code to do so this morning, long before your posting.

Could you explain the basic idea? Source code is not the clearest
possible tutorial.

I suspect CBFalconer has missed the discussion about "extra space".
The normal formal meaning of an "in place algorithm" is one that uses
O(1) extra storage and his code uses more than constant extra space.

As I think you suggested in a reply to Stephen Howe, this extra space
can probably be avoided if the list is doubly linked. I don't know
that algorithm, it just seem likely to exist!

Anyway, in case it was the algorithm itself rather than how to avoid
using the extra space that you were asking about, here is another view
of list-based merge sort. You need two sub-operations:

split(L) :- return two lists, neither longer than length(L)/2
containing, between them, the elements of L.

merge(L1, L2) :- return a list containing the elements of L1 and L2
such that if L1 and L2 are both sorted, the result is
sorted.

Both of these operations are linear in the length of the lists they
work with and both can be implemented with O(1) extra storage.
Merge sort is then defined as:

msort(L) = merge(msort(L1), msort(L2)) where L1, L2 = split(L).

This requires (in the normal course of events) O(log N) space for the
recursive calls.

As to the OP's original question, I doubt that any list-based sort
meets their definition of "in place". Even using the "needs O(1)
extra space" definition, just using a list requires O(N) extra space
in some sense.

--
Ben.
.

Relevant Pages

  • Re: Best stable sorting algorithm
    ... what is the fastest known algorithm to use to stable sort the ... array in-place and use no more than Oextra space? ... algorithm with best *theoretical* performance. ... compared to good implementations of quicksort that ...
    (comp.theory)
  • Re: In-place algorithm
    ... The normal formal meaning of an "in place algorithm" is one that uses ... Oextra storage and his code uses more than constant extra space. ... Both of these operations are linear in the length of the lists they ... Merge sort is then defined as: ...
    (comp.programming)
  • Re: In-place algorithm
    ... Oextra storage and his code uses more than constant extra space. ... Both of these operations are linear in the length of the lists they ... nodeptr mergesort(nodeptr root, ... mergesort(p, cmp), ...
    (comp.programming)
  • Re: Any problems with *lots* of attributes?
    ... >lists on a per item basis, ... >extra space so that they don't have to reallocate too frequently ... not in reams of trivial code that bores the reader to death." ...
    (comp.lang.python)
  • Re: Best stable sorting algorithm
    ... what is the fastest known algorithm to use to stable sort the ... array in-place and use no more than Oextra space? ... algorithm with best *theoretical* performance. ...
    (comp.theory)