using merge sort for a doubly linked list with its pointer

Question

Hi I want to sort a doubly linked list with its pointer and using merge sort algorithm,would you please help me that how can i do that? is there any link that have such a code? thanks

Answer 1

Ah that question surprisingly makes a little sense. So your doubly linked list is a bunch of "nodes"... each having a reference to the next node, previous node, and the data that the current node contains... correct? I think "pointer" has a very specific meaning that might confuse advanced programmers if you use it in this context. I think you are just talking about a reference to an object.

So your looking to write a merge sort that modifies the reference that previousNode and nextNode point to for each node in the doubly linked list.

Is this correct?

Do you already have your own doubly linked list class written?

Answer 2

Since this seems to be homework, I'll only provide some hints.

The general idea of merge sort is to do the following:

1. Split the input collection in the middle
2. Sort the two halves recursively
3. Merge the sorted halves

You should already have an idea how to do this efficiently when the input is an array (or other random access collection). When the input is a linked list, all you have to figure out is how to perform the split operation and the merge operation correctly.

Then, it could be a good idea to formulate the recurrence relation of your algorithm's running time, to make sure that it still runs in O(N log N) time, as expected.