Updated on

Merge sort is a divide and conquer sorting algorithm: it splits an array into halves until every piece holds one element, then merges the pieces back together in sorted order. All it needs in C# is one recursive method and one merge method, and it runs in O(N log N) time on any input.

Merge sort in C# is one of the algorithms that we can use to sort elements, and it is known to be efficient. Let’s implement it, count the work it does, and measure it.

To download the source code for this article, you can visit our GitHub repository.

Let’s start. 

What Is Merge Sort?

NIST’s Dictionary of Algorithms and Data Structures defines it this way: “A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence.”

Merge Sort achieves its purpose using a two-step process:

Divide: merge sort starts by dividing the input array into two halves. The algorithm recursively calls itself for each of those halves until there are no half-arrays to divide during the sorting process. 

Conquer: the algorithm sorts and merges the sub-arrays in this step to return an array whose values are sorted. 

Generally, we use these high-level steps when sorting an array or a list with a merge sort:

Step 1: Check if the array has one element. If it does, it means all the elements are sorted. 
Step 2: Use recursion to divide the array into two halves until we can't divide it anymore. 
Step 3: Merge the arrays into a new array whose values are sorted.

How Does Merge Sort Algorithm Work?

Let’s say we want to sort an array that has eight elements:

int[] array = { 73, 57, 49, 99, 133, 20, 1, 34 };

Dividing Arrays

Using the merge sort algorithm, let’s start subdividing the array into equal halves. We can see here that in the first iteration, the array is split into two equal arrays of half the size (4): 
73, 57, 49, 99 133, 20, 1, 34

Now, we divide these arrays into halves without changing the sequence of the elements in the original array:
73, 57  49, 99 133, 20 1, 34

We are going to subdivide the arrays further into arrays that have one element each (we achieve the atomic value in this step):
73  57 49  99  133  20  1  34

After subdividing the arrays, we are going to now start merging them while comparing the elements and placing them in the right order.

Merging and Sorting

This algorithm requires an extra array to store the sorted elements. The algorithm starts by traversing the subarrays that hold 73 and 57. 57 is less than 73, so we swap their positions while merging them into a new array that has two elements:
57, 73

Mind you, merging does not swap anything in place. It compares the first remaining element of each subarray and copies the smaller one into the next position of the merged array. What looked like swapping 57 and 73 is that same step on two subarrays of one element each.

Next, we traverse the subarrays that hold 49 and 99 while comparing the elements at each position. Since 49 is less than 99, the merged array of size 2 becomes: 
57, 73  49, 99

The same process applies here as the algorithm starts traversing the subarrays while comparing the values they hold in each position. 20 is less than 133, so the algorithm swaps their positions when merging them and the array becomes:
57, 73  49, 99 20, 133

1 and 34 are already in the correct order so we don’t swap their positions when combining them back into an array:
57, 73  49, 99 20, 133 1, 34

Next Merge Iteration

In the next iteration of the merging process, the arrays should have four elements each, sorted in the correct order. 

The algorithm starts traversing the two subarrays of size two while comparing the values at each position. In the first position, 49 is less than 57, so 49 goes first. Next, 57 is less than 99, so 57 goes second. Then 73 is less than 99, so 73 goes third, and 99, the only value left, goes last.

So, the new merged array of size 4 is:
49, 57, 73, 99

We repeat the same process for the right half of the array.

The algorithm compares the elements on each subarray while merging them into a new array. 1 is less than 20 so it becomes the first element in the merged array followed by 20.

The algorithm compares 133 with 34 and adds 34 first into the new array before adding 133. So, the new array after the merging process is:
1, 20, 34, 133

In the next iteration of the merging process, the array should have eight sorted elements (same as the original array). 

The algorithm starts traversing the subarrays while comparing the values at each position while adding them to a new array that has sorted elements. For example, at position 1 in the subarrays, 1 is less than 49, so we store 1 as the first element in the merged array:
49, 57, 73, 99 1, 20, 34, 133

The algorithm iterates through the arrays while placing them in the correct order in the merged array which becomes:  
1, 20, 34, 49, 57, 73, 99, 133

Here is the whole process in one picture.

A tree diagram. The array 73, 57, 49, 99, 133, 20, 1, 34 splits into halves three times until eight single elements remain, then pairs merge into 57, 73 / 49, 99 / 20, 133 / 1, 34, then into 49, 57, 73, 99 and 1, 20, 34, 133, and finally into 1, 20, 34, 49, 57, 73, 99, 133.

Merge sort on our eight-element array: the top half splits it down to single elements, the bottom half merges them back in order.

Let’s implement the merge sort algorithm in C#.

How to Implement Merge Sort in C#?

To implement merge sort in C#, we need two methods: a recursive one that splits the array and one that merges two sorted halves.

The recursive method takes the array and the indexes of the first and last element it should sort. If that range holds more than one element, it finds the middle index, calls itself for the left half and for the right half, and then merges the two.

The merge method copies both halves into two temporary arrays. It then walks them side by side, compares their first remaining elements, and writes the smaller one back into the original array. When one temporary array runs out, the rest of the other one is copied over unchanged.

A range with one element is already sorted, which is where the recursion stops.

The whole sort happens inside the array we pass in. The method returns that same array instance, so the caller’s array is sorted too.

We are going to define a method SortArray() in a Merge class of a new console app as our entry point into the sorting algorithm. The method takes three parameters int[] array, int left and int right:

public int[] SortArray(int[] array, int left, int right)
{
  if (left < right)
  {
    int middle = left + (right - left) / 2;

    SortArray(array, left, middle);
    SortArray(array, middle + 1, right);

    MergeArray(array, left, middle, right);
  }

  return array;
}

First, SortArray() uses the left and right integer values to define the index of the element in the middle of the array.

The method recursively calls itself to subdivide the right and left subarrays. The merging process commences as soon as the first two subarrays have one element each. Let’s write a method in the same class that implements the merge sort process:

public void MergeArray(int[] array, int left, int middle, int right)
{
  var leftArrayLength = middle - left + 1;
  var rightArrayLength = right - middle;
  var leftTempArray = new int[leftArrayLength];
  var rightTempArray = new int[rightArrayLength];
  int i, j;

  for (i = 0; i < leftArrayLength; ++i)
    leftTempArray[i] = array[left + i];
  for (j = 0; j < rightArrayLength; ++j)
    rightTempArray[j] = array[middle + 1 + j];

  i = 0;
  j = 0;
  int k = left;

  while (i < leftArrayLength && j < rightArrayLength)
  {
    if (leftTempArray[i] <= rightTempArray[j])
    {
      array[k++] = leftTempArray[i++];
    }
    else
    {
      array[k++] = rightTempArray[j++];
    }
  }

  while (i < leftArrayLength)
  {
    array[k++] = leftTempArray[i++];
  }

  while (j < rightArrayLength)
  {
    array[k++] = rightTempArray[j++];
  }
}

The first thing to note is that the MergeArray() method takes four parameters. The leftArrayLength and rightArrayLength variables help us define temporary arrays to hold values during the sorting process:

var leftArrayLength = middle - left + 1;
var rightArrayLength = right - middle;
var leftTempArray = new int[leftArrayLength];
var rightTempArray = new int[rightArrayLength];

We copy data into those temporary arrays using two loops as the next step:

for (i = 0; i < leftArrayLength; ++i)
  leftTempArray[i] = array[left + i];
for (j = 0; j < rightArrayLength; ++j)
  rightTempArray[j] = array[middle + 1 + j];

We then compare leftTempArray[i] with rightTempArray[j] and copy the smaller of the two into array[k]. When the two values are equal, the left one goes first, because the condition is <=, and that keeps equal values in their original order:

while (i < leftArrayLength && j < rightArrayLength)
{
  if (leftTempArray[i] <= rightTempArray[j])
  {
    array[k++] = leftTempArray[i++];
  }
  else
  {
    array[k++] = rightTempArray[j++];
  }
}

The process completes by copying any remaining elements from the leftTempArray and the rightTempArray arrays into the merged array:

while (i < leftArrayLength)
{
  array[k++] = leftTempArray[i++];
}

while (j < rightArrayLength)
{
  array[k++] = rightTempArray[j++];
}

Finally, in a test method of an MSTest project that references our app, we can verify that the method sorts an array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new Merge();

var sortedArray = sortFunction.SortArray(array, 0, array.Length - 1);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);

What Is the Time and Space Complexity of Merge Sort?

Merge sort runs in O(N log N) time in the best, average and worst case, and it needs O(N) extra space.

The log N part comes from the splitting. Halving an array until every piece holds one element takes about logâ‚‚ N levels of recursion, so for 2,000 elements our method goes 12 calls deep.

The N part comes from the merging. On every level, the merge step copies each element into a temporary array once and writes it back once.

Those temporary arrays are the O(N) extra space. During the final merge, they hold all N elements at the same time, and the recursion adds O(log N) stack space on top.

Merge sort is stable: equal values keep their original order, because our merge takes from the left subarray on a tie. It is not an in-place sort, because the merge needs those temporary arrays.

Let’s see why.

Assuming the length of the array is N, every time we divide it into equal halves, we can represent that process as a logarithmic function log N. In each step, we find the middle of any subarray, which takes O(1) time. 

As we merge the subarrays, the algorithm takes O(N) which we determine through the length of the array we are sorting. We can see those temporary arrays in the MergeArray() method from the implementation step.

Therefore, the total time that the merge sort algorithm takes is N(log N + 1), which we can convert to O(N*log N). 

The best, average, and worst-case complexity of the merge sort algorithm is O(N*log N). 

The best-case complexity scenario occurs when the algorithm sorts an array whose values are sorted. In this case, the number of comparisons the algorithm makes is close to minimal: for 2,000 sorted numbers, our method makes 11,088 comparisons, against 19,425 for random numbers. It still copies every element on every level, so the time stays O(N*log N).

When the elements are in random order, the algorithm encounters an average-case complexity scenario.

The worst-case complexity scenario is not a list in descending order, as we might expect. In a descending list, every element of the right subarray is smaller than the first element of the left one, so each merge stops comparing after half the elements. For 2,000 numbers that is 10,864 comparisons, even fewer than for a sorted array. The most comparisons come from an input where the values of the two halves interleave, so every merge compares until both subarrays are almost empty: 19,953 for 2,000 numbers. Even then, the algorithm stays at O(N*log N).

Advantages and Disadvantages of Merge Sort Algorithm

The merge sort algorithm is faster when sorting large arrays than other sorting algorithms such as bubble sort.

It has a consistent time complexity, as all the cases take O(N*log N) time. 

However, merge sort requires O(N) space to run, which makes it less memory efficient than bubble sort and selection sort which use constant space O(1). Besides that, on very small arrays the recursion and the temporary arrays cost more than they save, so simpler algorithms such as bubble sort and insertion sort are faster there. In a quick check on 8 and 16 random numbers, our merge sort was slower than both. If memory matters, quicksort uses the same divide and conquer idea but sorts the array in place, so it needs little extra memory beyond the recursion stack. Heap sort is the other common O(N*log N) choice. It sorts in place with no second array, but it is not stable.

Stability matters when we sort records by one key and want records with equal keys to keep their earlier order, for example orders sorted by date that were already sorted by customer. In production code, we don’t need our own merge sort for that, because LINQ’s OrderBy() is stable too. When two keys are equal, its sorter in the .NET runtime compares the elements’ original positions, and the source comment on that line reads “ensure stability of sort”. Our article on sorting a list by a property puts the stable and unstable options side by side.

How Does Merge Sort Perform on Random and Sorted Arrays?

Let’s verify the merge sort algorithm has a time complexity of O(N*log N) by measuring the time it takes for the algorithm to sort an array with BenchmarkDotNet.

First, let’s write a method in our Merge class to generate a set of random numbers that are going to be added into the array:

public static int[] GenerateRandomNumber(int size)
{
    var array = new int[size];
    var rand = new Random();
    var maxNum = 10000;

    for (int i = 0; i < size; i++)
        array[i] = rand.Next(maxNum + 1);

    return array;
}

The GenerateRandomNumber method takes an integer as its sole input. Using the inbuilt Random class, we generate integer values (from 0 to 10000) that we’re going to put into the array.

Let’s write a method in the same class that generates a sorted array:

public static int[] GenerateSortedNumber(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = i;

    return array;
}

Both methods give us arrays of random numbers or sorted numbers of any size.

Before we write the benchmark, there is one trap to avoid: SortArray() changes the array we hand it, and BenchmarkDotNet invokes the benchmark method over and over. Hand it the same array each time, and from the second call on, it merges numbers that are already in order.

The earlier version of this benchmark fell into exactly that trap, which is why its “Unsorted” and “Sorted” rows were almost identical. This time, Setup() builds each input once, and every call first copies it into _work and sorts the copy:

[MemoryDiagnoser]
public class MergeBenchmarks
{
    private readonly Merge _merge = new();
    private int[] _source = [];
    private int[] _work = [];

    [Params(200, 2_000, 20_000)]
    public int Size { get; set; }

    [Params("Random", "Sorted")]
    public string Input { get; set; } = "Random";

    [GlobalSetup]
    public void Setup()
    {
        _source = Input == "Random"
            ? Merge.GenerateRandomNumber(Size)
            : Merge.GenerateSortedNumber(Size);
        _work = new int[Size];
    }

    [Benchmark]
    public int[] SortArray()
    {
        _source.CopyTo(_work, 0);

        return _merge.SortArray(_work, 0, _work.Length - 1);
    }
}

BenchmarkDotNet calls Setup() before the timed calls, once for every Size and Input pair. The copy is O(N) work, a small extra next to the O(N log N) sort, and [MemoryDiagnoser] adds the memory columns we look at below.

The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<MergeBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and look at the results:

| Method    | Size  | Input  | Mean         | Error      | StdDev     | Gen0     | Gen1   | Allocated  |
|---------- |------ |------- |-------------:|-----------:|-----------:|---------:|-------:|-----------:|
| SortArray | 200   | Random |     4.660 us |  0.0726 us |  0.0713 us |   2.0142 |      - |   16.45 KB |
| SortArray | 200   | Sorted |     4.179 us |  0.0617 us |  0.0547 us |   2.0142 |      - |   16.45 KB |
| SortArray | 2000  | Random |   118.027 us |  1.1297 us |  1.0567 us |  22.9492 |      - |  188.14 KB |
| SortArray | 2000  | Sorted |    52.345 us |  0.5052 us |  0.4478 us |  23.0103 |      - |  188.14 KB |
| SortArray | 20000 | Random | 1,542.363 us | 11.3558 us |  9.4826 us | 265.6250 |      - | 2171.95 KB |
| SortArray | 20000 | Sorted |   606.220 us | 11.2611 us | 11.0599 us | 265.6250 | 0.9766 | 2171.95 KB |

On 2,000 and 20,000 numbers, sorting a sorted array takes less than half the time of sorting a random one. Fewer comparisons explain only a small part of that. On sorted input, every merge stops comparing as soon as the left subarray runs out, so the method makes about 43% fewer comparisons. Yet when we timed the interleaved input from the worst-case paragraph, which makes the most comparisons of all, it sorted about as fast as the sorted array. Both inputs follow a pattern the processor can learn: the if inside the merge loop always takes the same branch on sorted input and alternates on interleaved input. On random input, the processor has to guess which way it goes. At 200 numbers, the two inputs are only about 10% apart.

From 2,000 to 20,000, ten times more random numbers take a bit more than ten times longer, which is the O(N*log N) growth: about 0.12 milliseconds for 2,000 and about 1.5 milliseconds for 20,000. A quadratic sort such as bubble sort needs about a hundred times longer for the same step.

The Allocated column measures memory. To sort 20,000 numbers, which take about 78 KB, our method allocates about 2.1 MB, because every merge creates two new temporary arrays: 39,998 arrays in total. Only about one array’s worth of them is in use at any moment, which is why the space complexity is still O(N). The garbage collector has to clean up all of them anyway, as the Gen0 column shows.

Conclusion

Merge sort in C# is efficient when sorting large lists and arrays but needs extra space O(N) to achieve its goals. It uses the “divide and conquer” strategy, which makes it have a time complexity of O(N*log N). If you want to learn how to implement other sorting algorithms, check out these bubble sort and selection sort articles.

Merge sort keeps equal values in order and runs in O(N log N) on any input, at the cost of temporary arrays. In application code, we would still call Array.Sort() or List<T>.Sort(), and our quicksort article covers the algorithm behind them. For an O(N log N) sort that needs no extra array, take a look at heap sort.

Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.