Merge sort is a popular sorting algorithm that works by dividing an array into two halves, sorting each half, and then merging the two sorted halves back together. This algorithm is known for its efficiency and is often used in real-world applications where sorting large amounts of data is required. In this blog post, we will discuss how to implement a merge sort in C# and optimize it for performance.

Step 1: Understanding Merge Sort

Before we dive into the implementation, let’s take a quick look at how merge sort works. Merge sort follows a divide-and-conquer approach where it repeatedly divides the input array into two halves until each half contains only one element. Then it merges these sorted halves back together to form a single sorted array.

To achieve this, the algorithm uses a helper function, Merge, that takes in two sorted sub-arrays and combines them into a single sorted array. The merge function compares the first element of each sub-array and adds the smaller one to the new array. It then continues this process until one of the sub-arrays is completely added to the new array. Finally, it adds the remaining elements of the other sub-array to the new array.

Step 2: Implementing Merge Sort in C#

Now that we understand how merge sort works, let’s implement it in C#. First, we will create a function that divides the input array into two halves recursively.

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

In this code, we use the left and right parameters to denote the indices of the first and last elements of the array. The base case for the recursive function is when the left index is greater than or equal to the right index, which means that there is only one element in the sub-array.

Next, we implement the Merge function that we discussed earlier.

public static void Merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }

    while (i <= mid) {
        temp[k] = arr[i];
        i++;
        k++;
    }

    while (j <= right) {
        temp[k] = arr[j];
        j++;
        k++;
    }

    for (i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}

In this code, we first create a temporary array to store the merged sub-arrays. We then use three indices, i, j, and k, to keep track of the current position in the left sub-array, the right sub-array, and the temporary array, respectively.

We compare the elements at the current positions in the left and right sub-arrays and add the smaller one to the temporary array. We then increment the corresponding index and continue until one of the sub-arrays is completely added to the temporary array. Finally, we add the remaining elements of the other sub-array to the temporary array.

After merging the two sub-arrays, we copy the elements back to the original array from the temporary array.

Step 3: Optimizing Merge Sort for Performance

While the above implementation of Merge Sort in C# is correct, there are some optimizations we can make to improve its performance. One such optimization is to use an insertion sort for small sub-arrays instead of continuing to recursively divide the array.

private const int InsertionSortThreshold = 16;

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

private static void InsertionSort(int[] arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

In this code, we introduce a new constant, InsertionSortThreshold, which determines the maximum size of the sub-arrays that will be sorted using insertion sort instead of merge sort. If the size of the sub-array is smaller than or equal to this threshold, we use an insertion sort.

Insertion sort has a lower overhead than merge sort, which makes it faster for small sub-arrays. Therefore, by using an insertion sort for small sub-arrays and merge sort for larger sub-arrays, we can optimize the performance of the overall algorithm.

Step 4: Testing the Merge Sort Implementation

Finally, let’s test our implementation of merge sort to ensure that it is working correctly.

int[] arr = { 5, 3, 8, 4, 2, 7, 1, 6 };
MergeSort(arr, 0, arr.Length - 1);
foreach (int i in arr) {
    Console.Write(i + " ");
}

In this code, we create an array of unsorted integers and call the MergeSort function with the left and right indices. After the function call, we print the sorted array to the console.

In this blog post, we discussed how to implement a merge sort in C# and optimize it for performance. We also discussed how merge sort works and why it is a popular sorting algorithm. By using a divide-and-conquer approach and a merge function, merge sort can sort large amounts of data efficiently. With the added optimization of using an insertion sort for small sub-arrays, we can further improve its performance.