Merge sort without extra memory

Question

is there any condition in which the merge sort can be performed without additional memory, my professor said he had, and he would give a bonus ball.

Answer 1

You want google to host merge sort.

Here is one of the results: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html

Answer 2

Given that this is a homework question, I can only point out the art of programming. A good programmer should be able to use standard links in our field to investigate such a question.

Answer 3

,

Answer 4

Use linked list. This avoids the extra O (n) space needed when merging the two lists. However, you cannot do anything about the space occupied by recursion calls ie O (lg (n)).