First, let me describe two button-up ways to merge-sort a single linked list:
- Merge two elements, push that on a stack. Merge the next two elements, pop, merge and push. Merge two elements, push, merge two, pop, merge, pop, merge, push. I hope you got the idea.
- Merge with the next element, move 2. Merge, move 2. If you arrived at the end of the list, do it again, but with doubled step size. Repeat until the list is sorted (this is when the step size is greater than the list size).
As you can see, version (2) does not require additional space, but you have to do more steps in the linked list you wouldn't need (if step size is 4, e.g., you have to step 4 times until the next operation). Version (1) traverses the list only once, but needs log2(n) additional memory for the stack.
Can you tell me what the time difference between both versions is, how much slower is version 2? Is it constant time and why?
Is there a version of mergesort which has both benefits?
Thanks.