C# Program to Perform Merge Sort on an Array

A C# program for merge sort uses a MergeSort method to recursively split the array and a Merge method to combine sorted parts; for example, MergeSort(arr, 0, arr.Length - 1) sorts the array in place.

Examples

Input[5, 3, 8, 4, 2]

Output[2, 3, 4, 5, 8]

Input[1]

Output[1]

Input[]

Output[]

How to Think About It

To sort an array with merge sort, first split the array into two halves until each part has one or zero elements. Then, merge these small parts back together in sorted order by comparing elements from each half. This process repeats until the whole array is sorted.

Algorithm

1

Check if the array section has more than one element; if not, return.

2

Find the middle index to split the array into two halves.

3

Recursively apply merge sort to the left half.

4

Recursively apply merge sort to the right half.

5

Merge the two sorted halves into one sorted section.

Code

csharp

using System;

class Program {
    static void Merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int a = 0, b = 0, k = left;
        while (a < n1 && b < n2) {
            if (L[a] <= R[b]) arr[k++] = L[a++];
            else arr[k++] = R[b++];
        }

        while (a < n1) arr[k++] = L[a++];
        while (b < n2) arr[k++] = R[b++];
    }

    static void MergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);
            Merge(arr, left, mid, right);
        }
    }

    static void Main() {
        int[] arr = {5, 3, 8, 4, 2};
        MergeSort(arr, 0, arr.Length - 1);
        Console.WriteLine(string.Join(", ", arr));
    }
}

Output

2, 3, 4, 5, 8

Dry Run

Let's trace sorting the array [5, 3, 8, 4, 2] through the merge sort code.

1

Split array

Split [5, 3, 8, 4, 2] into [5, 3, 8] and [4, 2]

2

Split left half

Split [5, 3, 8] into [5, 3] and [8]

3

Split left-left half

Split [5, 3] into [5] and [3]

4

Merge [5] and [3]

Merge to get [3, 5]

5

Merge [3, 5] and [8]

Merge to get [3, 5, 8]

6

Split right half

Split [4, 2] into [4] and [2]

7

Merge [4] and [2]

Merge to get [2, 4]

8

Merge [3, 5, 8] and [2, 4]

Merge to get [2, 3, 4, 5, 8]

Step	Array State
Initial	[5, 3, 8, 4, 2]
Split	[5, 3, 8] and [4, 2]
Split	[5, 3] and [8]
Split	[5] and [3]
Merge	[3, 5]
Merge	[3, 5, 8]
Split	[4] and [2]
Merge	[2, 4]
Merge	[2, 3, 4, 5, 8]

Why This Works

Step 1: Divide the array

The code splits the array into smaller parts using MergeSort recursively until each part has one element.

Step 2: Merge sorted parts

The Merge method combines two sorted arrays by comparing elements and placing the smaller one first.

Step 3: Complete sorting

Repeated splitting and merging results in a fully sorted array when the recursion finishes.

Alternative Approaches

Iterative Merge Sort

csharp

using System;
class Program {
    static void Merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
        int a = 0, b = 0, k = left;
        while (a < n1 && b < n2) {
            if (L[a] <= R[b]) arr[k++] = L[a++];
            else arr[k++] = R[b++];
        }
        while (a < n1) arr[k++] = L[a++];
        while (b < n2) arr[k++] = R[b++];
    }

    static void MergeSort(int[] arr) {
        int n = arr.Length;
        for (int currSize = 1; currSize <= n - 1; currSize *= 2) {
            for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
                int mid = Math.Min(leftStart + currSize - 1, n - 1);
                int rightEnd = Math.Min(leftStart + 2 * currSize - 1, n - 1);
                Merge(arr, leftStart, mid, rightEnd);
            }
        }
    }

    static void Main() {
        int[] arr = {5, 3, 8, 4, 2};
        MergeSort(arr);
        Console.WriteLine(string.Join(", ", arr));
    }
}

This approach avoids recursion but is more complex to understand and implement.

Using List and LINQ

csharp

using System;
using System.Collections.Generic;
using System.Linq;
class Program {
    static List<int> MergeSort(List<int> list) {
        if (list.Count <= 1) return list;
        int mid = list.Count / 2;
        var left = MergeSort(list.Take(mid).ToList());
        var right = MergeSort(list.Skip(mid).ToList());
        return Merge(left, right);
    }
    static List<int> Merge(List<int> left, List<int> right) {
        List<int> result = new List<int>();
        int i = 0, j = 0;
        while (i < left.Count && j < right.Count) {
            if (left[i] <= right[j]) result.Add(left[i++]);
            else result.Add(right[j++]);
        }
        result.AddRange(left.Skip(i));
        result.AddRange(right.Skip(j));
        return result;
    }
    static void Main() {
        var arr = new List<int>{5, 3, 8, 4, 2};
        var sorted = MergeSort(arr);
        Console.WriteLine(string.Join(", ", sorted));
    }
}

This method uses lists and LINQ for clarity but uses more memory due to list copies.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time.

Space Complexity

It requires extra space to hold temporary arrays during merging, so space complexity is O(n).

Which Approach is Fastest?

Recursive merge sort is easier to understand and widely used; iterative merge sort avoids recursion overhead but is more complex; using lists and LINQ is clearer but uses more memory.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	General purpose, easy to implement
Iterative Merge Sort	O(n log n)	O(n)	Avoid recursion, large data sets
List + LINQ Merge Sort	O(n log n)	O(n)	Readability, functional style