Re: In-place algorithm

Ben Bacarisse wrote:
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.

I think that the spirit of the request is that the algorithm should
not take additional memory besides what the list already is taking. In
other words, no more than O(1) amount of memory is allocated for the
merge sort algorithm itself.

Granted, technically speaking merge sort always requires additional
memory to work. But in the case of a doubly-linked list the existing
pointers can be used as this additional memory, so no additional memory
*besides them* is needed.
.

Relevant Pages

  • Re: [PATCH 4/4] mm: variable length argument support
    ... Please do remember that if the memory ... any time invalidate the number which the kernel now holds. ... the string will munge into the following string. ... > + * the stack is optionally relocated, and some extra space is added. ...
    (Linux-Kernel)
  • Re: In-place algorithm
    ... extra space" definition, just using a list requires Oextra space ... not take additional memory besides what the list already is taking. ... Mergesort is a divide and conquer algorithm; ... linked lists. ...
    (comp.programming)
  • Re: Un DIMing a DIMed variable
    ... If you're loading a file into a block of memory, ... Using RMA blocks for variable size application data? ... You can do dynamic memory management in BASIC. ... For instance, to set the extra space to X, you ...
    (comp.sys.acorn.programmer)
  • Re: Typical Disk Slicing Practices
    ... >>Just curious how other admins slice up the system disks and why. ... > On a recently installed system, ... Some people swear by 2X memory. ... Just go with the recommended size and tack on extra space for ...
    (comp.sys.sun.admin)
  • Re: In-place algorithm
    ... extra space" definition, just using a list requires Oextra space ... not take additional memory besides what the list already is taking. ... the merge sort algorithm itself. ... technically speaking merge sort always requires additional ...
    (comp.programming)