I came across this problem yesterday. Here are some thoughts.
Sorting a DoublyLinkedList is different from sorting an Array as you can not make index based references to any arbitrary item in the List. Instead you need to remember the items during each recursive step and then pass them on to the merge function. For each recursion step you only need to remember the first item of each list half. If you do not remember these items you will quickly end up with indexes, but this leads you to the problem that in your merge-function you need to traverse the whole list with for-loops to find the items to merge. That in turn means you get a complexity of O(n^2).
Another important point is the step of recursing into the list and dividing the list in two halves. You can do this step in the recursive part by using for-loops. Contrary to the merge-part at this step the for-loops will only yield a complexity of O(log(n) * n/2) and this is still below the overall O(n*log(n)) complexity. Here is why:
You always need to find the first item of each half of list part.
In the first recursion step you need to pass the first item and the item at position n/2. This takes n/2 steps to find.
In each following step you need to find the middle item for each of the two halves of the list which gives us n/4 to find the item in the first halve and n/4 in the other halve. In total thats n/2.
In each following recursive step the amount of list parts double and the lengths is divided by two:
The recursion depth is log(n) and in each step we perform n/2 steps. This equals O(log(n)*n/2)
Finally here is some code:
public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
in.first = mergesort(in.first, numOfElements);
return in;
}
mergeSort:
public ListElement mergesort(ListElement first, int length) {
if(length > 1) {
ListElement second = first;
for(int i=0; i<length/2; i++) {
second = second.next;
}
first = mergesort(first, length/2);
second = mergesort(second, (length+1)/2);
return merge(first, second, length);
} else {
return first;
}
}
and merge:
public ListElement merge(ListElement first, ListElement second, int length) {
ListElement result = first.prev; //remember the beginning of the new list will begin after its merged
int right = 0;
for(int i=0; i<length; i++) {
if(first.getKey() <= second.getKey()) {
if(first.next == second) break; //end of first list and all items in the second list are already sorted, thus break
first = first.next;
} else {
if(right==(length+1)/2)
break; //we have merged all elements of the right list into the first list, thus break
if(second == result) result = result.prev; //special case that we are mergin the last element then the result element moves one step back.
ListElement nextSecond = second.next;
//remove second
second.prev.next = second.next;
second.next.prev = second.prev;
//insert second behind first.prev
second.prev = first.prev;
first.prev.next = second;
//insert second before first
second.next = first;
first.prev = second;
//move on to the next item in the second list
second = nextSecond;
right++;
}
}
return result.next; //return the beginning of the merged list
}
The maximum amount of memory used is also pretty low (not including the list itself). Correct me if I'm wrong but it should be less than 400 bytes (on 32bit). It would be 12 byte per call on mergeSort times the recursion depth of log(n) plus 20 bytes for the variables of merge thus: 12*log(n)+20 bytes.
P.S. Code tested on 1 million items (takes 1200ms). Also DoublyLinkedList is a container that stores the first ListElement of the list.
Update:
I have answered a similar question about Quicksort using the same data structures, however in comparison to this Mergesort implementation it runs much slower. Here are some updated timings for reference:
Mergesort:
1.000.000 Items: 466ms
8.300.000 Items: 5144ms
Quicksort:
1.000.000 Items: 696ms
8.300.000 Items: 8131ms
Note the timings are specific to my hardware and you might get different results.
