**Merge Sort**

Merge sort works by comparing every two elements and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Merge sort uses recursion for sorting the list.

The implementation of ** MergeSorter** class

public class MergeSorter

{

List

public List

{

List

tempList = new List

for (int i = 0; i <>

tempList.Add(default(T));

MergeSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void Merge(ref List

{

int i;

int j;

for (i = middle + 1; i > left; i--)

{

tempList[i - 1] = inputList[i - 1];

}

for (j = middle; j <>

{

tempList[right + middle - j] = inputList[j + 1];

}

for (int k = left; k <= right; k++)

{

// Less Than

if (tempList[j].CompareTo(tempList[i]) == -1)

{

inputList[k] = tempList[j--];

}

else

{

inputList[k] = tempList[i++];

}

}

}

private void MergeSort(ref List

{

if (right <= left) return;

int middle = (right + left) / 2;

//recursive sorting

MergeSort(ref a, left, middle);

MergeSort(ref a, middle + 1, right);

Merge(ref a, left, middle, right);

}

}

**Heap Sort**

The heap sort works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a binary tree (heap). Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.

The implementation of ** HeapSorter** class

public class HeapSorter

{

public List

{

List

HeapSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void HeapSort(ref List

{

int left = start + ((end - start) >> 1);

int right = end;

int offset = start;

while (left >= start)

{

SiftDown(items, offset, left, end);

left -= 1;

}

while (right > start)

{

Swap(items, right, start);

right -= 1;

SiftDown(items, offset, start, right);

}

}

private void SiftDown (List

{

int root = start;

int child;

while (((root - offset) * 2 + 1) <= (end - offset))

{

child = ((root - offset) * 2 + 1) + offset;

if (child <>

{

child += 1;

}

if (inputItems[root].CompareTo(inputItems[child]) <>

{

Swap(inputItems, root, child);

root = child;

}

else

{

break;

}

}

}

private void Swap (List

{

T swap = inputItems[i];

inputItems[i] = inputItems[k];

inputItems[k] = swap;

}

}

**Quick Sort**

Quick sort uses the algorithm that partitions an array to choose an element, called a *pivot*, move all smaller elements before the pivot, and move all greater elements after it. It then uses recursion to follow the same algorithm to finally create a sorted list of elements.

The implementation of ** QuickSorter** class

public class QuickSorter

{

public List

{

List

QuickSort(ref sorteditems, 0, sorteditems.Count - 1);

return sorteditems;

}

private void QuickSort(ref List

{

if (right <= left) return;

int i = Partition(ref sortedItems, left, right);

QuickSort(ref sortedItems, left, i - 1);

QuickSort(ref sortedItems, i + 1, right);

}

private int Partition(ref List

{

T tmp;

int i = l - 1;

int j = r;

T v = a[r]; for (; ; )

{

while (a[++i].CompareTo(v) == -1)

{

}

while (v.CompareTo(a[--j]) == -1)

{

if (j == l) break;

}

if (i >= j) break;

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

a[r] = a[i];

a[i] = v;

return i;

}

}

In the next series of this article, i will show how to use strategy pattern to select the sorting algorithms we have implemented.
## 2 comments:

Great !!! Thanks.

Hey,

useful algorithm!

In the heap sort, in the SiftDown method, you forgot some elements:

if (child <>

and

if (inputItems[root].CompareTo(inputItems[child]) <>

Can you please complete the code? Thanks!!

Post a Comment