< Summary

Information
Class: MoreStructures.Lists.Sorting.MergeSort
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/MergeSort.cs
Line coverage
100%
Covered lines: 30
Uncovered lines: 0
Coverable lines: 30
Total lines: 143
Line coverage: 100%
Branch coverage
100%
Covered branches: 10
Total branches: 10
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
Sort(...)100%1100%
Sort(...)100%1100%
RecursiveSort(...)100%2100%
Merge(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Sorting/MergeSort.cs

#LineLine coverage
 1using MoreStructures.Lists.Sorting.QuickSort;
 2
 3namespace MoreStructures.Lists.Sorting;
 4
 5/// <summary>
 6/// An <see cref="IInputMutatingSort"/> implementation based on the merge sort algorithm.
 7/// </summary>
 8/// <remarks>
 9///     <para id="advantages">
 10///     ADVANTAGES AND DISADVANTAGE
 11///     <br/>
 12///     - Compared to <see cref="SelectionSort"/> and <see cref="InsertionSort"/>, it has asymptotically better
 13///       runtime, linearithmic instead of quadratic.
 14///       <br/>
 15///     - Compared to <see cref="RecursiveQuickSort"/>, it has <b>better worst-case performance</b>: linearithmic, inste
 16///       quadratic.
 17///       <br/>
 18///     - In general <see cref="MergeSort"/> does a number of comparisons which is independent from the
 19///       input, whereas the number of comparisons in <see cref="RecursiveQuickSort"/> depends on the input and in parti
 20///       the choice of the pivot.
 21///       <br/>
 22///     - Unlike <see cref="SelectionSort"/>, <see cref="RecursiveQuickSort"/> and <see cref="ShellSort"/>, and like
 23///       <see cref="InsertionSort"/> it is a <b>stable</b> sorting algorithm, so it preserves the order in the input
 24///       of items with the same key.
 25///       <br/>
 26///     - A disadvantage over many other sorting algorithms, such as <see cref="SelectionSort"/>,
 27///       <see cref="InsertionSort"/>, <see cref="ShellSort"/> and <see cref="RecursiveQuickSort"/>, is that it is <b>no
 28///       in place</b>, as it requires additional O(n) space to perform the sorting.
 29///       <br/>
 30///     - An advantage over many other sorting algorithms, and in particular over <see cref="RecursiveQuickSort"/>, is t
 31///       is <b>easily parallelizable</b>.
 32///       <br/>
 33///     - The reason is that <see cref="MergeSort"/> is based on a "divide and conquer" design, where the partition of
 34///       the problem in sub-problems is done in O(1) time (just split the array in two halves) while the combine phase
 35///       (i.e. the merge) is more complex, taking O(n) time. In <see cref="RecursiveQuickSort"/> it is rather the oppos
 36///       partition is the O(n) operation, while the combine comes for free.
 37///       <br/>
 38///     - Another advantage of <see cref="MergeSort"/> over other comparison-based algorithms is that it performs an
 39///       <b>optimal number of comparisons</b>: n * log(n). No other comparison-based algorithm can do better. That,
 40///       however, doesn't mean that <see cref="MergeSort"/> performs better than any other comparison-based algorithm:
 41///       while <see cref="RecursiveQuickSort"/> performs more comparisons in average (~ 39% more, in practice), it also
 42///       sorting in place and does many less operations, resulting in better performance.
 43///       <br/>
 44///     - <see cref="MergeSort"/> becomes the best sorting algorithm in scenarios where random access to the input is
 45///       particular expensive, which can be the case for "sequential implementations" of <see cref="IList{T}"/>. An
 46///       example would be <see cref="LinkedList{T}"/>: while linked lists cannot provide O(1) random access, and for
 47///       that reason don't implement the <see cref="IList{T}"/> interface, an adapter of <see cref="LinkedList{T}"/>
 48///       to <see cref="IList{T}"/> would benefit from the items access pattern of <see cref="MergeSort"/> over
 49///       <see cref="RecursiveQuickSort"/>.
 50///     </para>
 51///     <para id="algorithm">
 52///     ALGORITHM
 53///     <br/>
 54///     - The algorithm uses a "divide et conquer" approach, recursively splitting the list to sort of size n in two
 55///       halves of size roughly n / 2 and using an auxiliary structure to merge the two sorted halves into a single
 56///       sorted list.
 57///       <br/>
 58///     - Before starting the recursion over the list to sort L, a temporary array T, of the same size n of L, is
 59///       instantiated, to be used for merging of sorted halves.
 60///       <br/>
 61///     - Then the recursive merge call is made, passing L, A and lower and upper indexes equal to 0 and n - 1
 62///       respectively.
 63///       <br/>
 64///     - Each recursive call split its input, which corresponds to the window of L from the lower to the upper index
 65///       into two halves, which are then recombined using A.
 66///     </para>
 67///     <para id="complexity">
 68///     COMPLEXITY
 69///     <br/>
 70///     - Every recursive call splits the input into two halves of roughly equal size.
 71///       <br/>
 72///     - Therefore, the depth of recursion is the logarithm of n in base 2.
 73///       <br/>
 74///     - Each recursive call performs an amount of work which is linear in the size of its input, and also uses a
 75///       linear amount of additional space in T, which, however, is instantiated once, at top level.
 76///       <br/>
 77///     - Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(n).
 78///     </para>
 79/// </remarks>
 80public class MergeSort : IInputMutatingSort
 81{
 82    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 83    /// <summary>
 84    ///     <inheritdoc/>
 85    ///     <br/>
 86    ///     Uses the merge sort algorithm with the default comparer for <typeparamref name="T"/>, given by
 87    ///     <see cref="Comparer{T}.Default"/>.
 88    /// </summary>
 89    /// <remarks>
 90    ///     <inheritdoc cref="MergeSort"/>
 91    /// </remarks>
 92    public void Sort<T>(IList<T> list) where T : IComparable<T> =>
 1993        Sort(list, Comparer<T>.Default);
 94
 95    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 96    /// <summary>
 97    ///     <inheritdoc/>
 98    ///     <br/>
 99    ///     Uses the merge sort algorithm with the specified <paramref name="comparer"/>.
 100    /// </summary>
 101    /// <remarks>
 102    ///     <inheritdoc cref="MergeSort"/>
 103    /// </remarks>
 104    public void Sort<T>(IList<T> list, IComparer<T> comparer)
 23105    {
 23106        var temp = list.ToArray();
 23107        RecursiveSort(list, temp, comparer, 0, list.Count - 1);
 23108    }
 109
 110    private static void RecursiveSort<T>(
 111        IList<T> list, IList<T> temp, IComparer<T> comparer, int startIndex, int endIndex)
 267112    {
 267113        if (endIndex <= startIndex)
 145114            return;
 115
 122116        var middleIndex = startIndex + (endIndex - startIndex) / 2;
 122117        (temp, list) = (list, temp); // Swap roles of list and temp
 122118        RecursiveSort(list, temp, comparer, startIndex, middleIndex);
 122119        RecursiveSort(list, temp, comparer, middleIndex + 1, endIndex);
 122120        Merge(temp, list, comparer, startIndex, middleIndex, endIndex);
 267121    }
 122
 123    private static void Merge<T>(
 124        IList<T> targetList, IList<T> sourceList, IComparer<T> comparer, int startIndex, int middleIndex, int endIndex)
 122125    {
 122126        var k1 = startIndex;
 122127        var k2 = middleIndex + 1;
 122128        var k = startIndex;
 526129        while (k <= endIndex)
 404130        {
 404131            if (k1 > middleIndex)
 155132                targetList[k] = sourceList[k2++];
 249133            else if (k2 > endIndex)
 18134                targetList[k] = sourceList[k1++];
 231135            else if (comparer.Compare(sourceList[k1], sourceList[k2]) <= 0)
 197136                targetList[k] = sourceList[k1++];
 137            else
 34138                targetList[k] = sourceList[k2++];
 139
 404140            k++;
 404141        }
 122142    }
 143}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

Sort(System.Collections.Generic.IList`1<T>)
Sort(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>)
RecursiveSort(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>,System.Int32,System.Int32)
Merge(System.Collections.Generic.IList`1<T>,System.Collections.Generic.IList`1<T>,System.Collections.Generic.IComparer`1<T>,System.Int32,System.Int32,System.Int32)