## 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