Merge sort in Linked list

[Ogakor]

Hello, I've been having problem with understanding merge sort for linked list. I understood merge sort for array though, I think. I've googled it and all I can find are codes. I need to understand the algorithm first before I can understand the code.
Please help me understand merge sort for linked list.

So in array, you copy the elements of the supposed-to-be-sorted-array to another array then through recursion, logically divide the elements until there are two elements left (I think you'll just move the pointers through recursion). Then sort the divided halves.
Illustration:
Divide
7 5 1 0 29 2 12
7 5 1 0 | 29 2 12
7 5 | 1 0 | 29 2 | 12
and Conquer
5 7 | 0 1 | 2 29 | 12
0 1 5 7 | 2 12 29
0 1 2 5 7 12 29
Am I correct?? I only want to verify.. Please answer.

So in link list, am I supposed to follow the same idea?
Should I just move the pointers at the middle of list and repeat until there are two elements left? Then sort it?
Please answer.

[N1GHTS]

I believe the concept of a linked list is that there are many sub lists inside one big list, with each element of the lists randomly scattered within the array, yet linked by pointers to the next element somewhere in the chaos of scattered elements in an effort for some program to add new sub lists to the holes in the list. Tell me if that sounds incorrect to you.

If it were just one big linked list with its elements randomly scattered around, the idea is to sort the link index using the merge algorithm as you would a simple array of disorganized numbers, but every time you switch two numbers in the list to sort it, you must also switch its Data element (Since a linked list is linking a series of pieces of data). So instead of just sorting indexes, you also blindly sort its payload without ever looking inside of it.

[Data:84, Index:3] [Data:16, Index:1] [Data:0, Index:2]

Using the Index in the merge algorithm, Switch 3 and 1:

[Data:16, Index:1] [Data:84, Index:3] [Data:0, Index:2]

Now finish the sort:

[Data:16, Index:1] [Data:0, Index:2] [Data:84, Index:3]

I just sorted a simple linked list, or at least that's the general idea.

Now if you are dealing with multiple sub lists, the trick is to identify each sub list by scanning the array while filling a series of new arrays that each have pointers to each sub list. So then you would end up with an array of arrays, each array being pointers to the sub lists found in the big random list of linked items.

Sorting that kind of complex list requires using the array of pointers as a "filter" so you can only sort each sub list one at a time without affecting the other elements of other linked lists. Then you need to loop through each array of pointers, copy each element in each sorted sub array to a whole new array with each sub list linked together and sorted in order. The sub lists, being valueless by themselves, will technically be in a random order among the other lists of the final array, but the elements of each sub list are sorted, and by that definition I would assume the whole linked list would be defined as sorted.

I did skip a bunch of details but I think you get the idea.

EDIT:

Oh and as far as the merge concept, you have it right. I might be wrong but I believe that after you subdivide the whole list to very tiny lists, the algorithm used is basically bubble sort, but someone correct me if i'm wrong.

[Narue]

>Am I correct?? I only want to verify.. Please answer.
Pretty much, yes.

>So in link list, am I supposed to follow the same idea?
The underlying concept doesn't change. However, note that while arrays give you fast random access, linked lists aren't nearly as forgiving. One benefit of merge sort is that you can sort streamed data in an efficient manner, and traversal of a linked list can be viewed as a stream. I'd suggest looking up information about a "natural" merge sort, which is better suited to sequential lists than the usual array-based merge sort (which is optimized for random access lists).

[Martin B]

I should add that you could also consider sorting a linked list by turning it into a binary tree and then back into a list again.

Sorting a linked list by turning it into a binary tree