Daniel Sapoundjiev on
Conquer sort - Sorting of linked lists
Sorting of linked lists
1 Feb 2013
Linked lists are special kind of lists, where every node points to the next node in the sequence. And for double linked lists every node points to the previous node too. More information in the wiki http://en.wikipedia.org/wiki/Linked_list
Most programming languages have their LinkedList classes. In java and C# it is called LinkedList. Interesting is that to the current moment I don't know about linked list coming standard with Delphi. In java and C# this LinkedList class represents double linked lists.
In java you can not access the node object. So every time when you want to make some operation with the list it searches for the node. That is because you have to pass the Object, and you can not pass the node directly. Which is a major disadvantage. In C# they did it better and allow passing nodes to the different methods and skipping the search.
Linked lists are different and different sorting algorithms gives different results. If the algorithm needs to move hundreds of items at a time it will be very fast with linked list and very slow with array list.
Different sorting algorithms performs differently depending on the initial data that will be sort. Some of them are fast when the items are almost sorted.
The algorithm characteristics
The algorithm I represent is like the merge sort algorithm with modifications. It is divide and conquer algorithm. But it divides the items in different way.
Memory used by the algorithm to process
During the execution the algorithm will need to allocate data. The number of these data items can be maximum log(2)N.Where N is the number of the elements that will be sorted. Here the algorithm can be optimized, but will left these for later. log(2)N is very good value too!
We need to keep the info for current ordered sequences in data
items. This is the memory the algorithm needs to process. First we
keep info for element 1 and 2 in one data item and in second data
item we keep the info for 3 and 4. After merging them we keep the
data only in data item 1 and the second data item is now free for
use. Then for elements 5 and 6 we use data item 2 and for elements
7 and 8 we use data item 3. After merging them we use only data
item 2 and data item 3 is free for use. Then we merge the elements
in data item 1 and 2. This way only data item 1 left. So to sort 8
elements we need 3 data items. For 16 elements we will need one
more data item, total of 4 data items. If we continue to double
the elements we have
Used memory is even less cause often we put 3 items in one data item.
In the current implementation we use buffered set of 100 data items which allows us to sort very big number This restriction is not necessary, so it is subject to further development to remove it. Also creating of these items can be skipped.
Number of comparisons
The best case is N-1 compares
Average is N*log(2)N
Worst is ...
Algorithm is Stable.
If you want fast sorting I suggest using Single Linked List!
Exe demo for Windows
LinkedListSorter.zip- size 402 KB
C# source code
Delphi source code
Java source code
Comming soonBack to main menu