Conquer sort

Sorting of linked lists

1 Feb 2013

Background information

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
2 - 1
4 - 2
8 - 3
16 - 4
32 - 5
64 - 6
128- 7
256- 8
512- 9
1024-10
For doubling the elements we add one more data item.
This is log(2)N
D = log(2)N where D are the count of the data items needed for sorting N elements

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.

In conclusion

If you want fast sorting I suggest using Single Linked List!

The algorithm

Comming soon

Exe demo for Windows

LinkedListSorter.zip- size 402 KB

C# source code

Comming soon

Delphi source code

LinkedListConquerSort.pas

Java source code

Comming soon

Back to main menu