Class MergeSort

An IInputMutatingSort implementation based on the merge sort algorithm.

Inheritance
System.Object
MergeSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting
Assembly: MoreStructures.dll
Syntax
public class MergeSort : IInputMutatingSort
Remarks

ADVANTAGES AND DISADVANTAGE
- Compared to SelectionSort and InsertionSort, it has asymptotically better runtime, linearithmic instead of quadratic.
- Compared to RecursiveQuickSort, it has better worst-case performance: linearithmic, instead of quadratic.
- In general MergeSort does a number of comparisons which is independent from the input, whereas the number of comparisons in RecursiveQuickSort depends on the input and in particular on the choice of the pivot.
- Unlike SelectionSort, RecursiveQuickSort and ShellSort, and like InsertionSort it is a stable sorting algorithm, so it preserves the order in the input of items with the same key.
- A disadvantage over many other sorting algorithms, such as SelectionSort, InsertionSort, ShellSort and RecursiveQuickSort, is that it is not in place, as it requires additional O(n) space to perform the sorting.
- An advantage over many other sorting algorithms, and in particular over RecursiveQuickSort, is that it is easily parallelizable.
- The reason is that MergeSort is based on a "divide and conquer" design, where the partition of the problem in sub-problems is done in O(1) time (just split the array in two halves) while the combine phase (i.e. the merge) is more complex, taking O(n) time. In RecursiveQuickSort it is rather the opposite: the partition is the O(n) operation, while the combine comes for free.
- Another advantage of MergeSort over other comparison-based algorithms is that it performs an optimal number of comparisons: n * log(n). No other comparison-based algorithm can do better. That, however, doesn't mean that MergeSort performs better than any other comparison-based algorithm: while RecursiveQuickSort performs more comparisons in average (~ 39% more, in practice), it also does sorting in place and does many less operations, resulting in better performance.
- MergeSort becomes the best sorting algorithm in scenarios where random access to the input is particular expensive, which can be the case for "sequential implementations" of . An example would be : while linked lists cannot provide O(1) random access, and for that reason don't implement the interface, an adapter of to would benefit from the items access pattern of MergeSort over RecursiveQuickSort.

ALGORITHM
- The algorithm uses a "divide et conquer" approach, recursively splitting the list to sort of size n in two halves of size roughly n / 2 and using an auxiliary structure to merge the two sorted halves into a single sorted list.
- Before starting the recursion over the list to sort L, a temporary array T, of the same size n of L, is instantiated, to be used for merging of sorted halves.
- Then the recursive merge call is made, passing L, A and lower and upper indexes equal to 0 and n - 1 respectively.
- Each recursive call split its input, which corresponds to the window of L from the lower to the upper index into two halves, which are then recombined using A.

COMPLEXITY
- Every recursive call splits the input into two halves of roughly equal size.
- Therefore, the depth of recursion is the logarithm of n in base 2.
- Each recursive call performs an amount of work which is linear in the size of its input, and also uses a linear amount of additional space in T, which, however, is instantiated once, at top level.
- Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(n).

Methods

| Improve this Doc View Source

Sort<T>(IList<T>)


Uses the merge sort algorithm with the default comparer for T, given by .

Declaration
public void Sort<T>(IList<T> list)
    where T : IComparable<T>
Parameters
Type Name Description
IList<T> list
Type Parameters
Name Description
T
Remarks

| Improve this Doc View Source

Sort<T>(IList<T>, IComparer<T>)


Uses the merge sort algorithm with the specified comparer.

Declaration
public void Sort<T>(IList<T> list, IComparer<T> comparer)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods