Merge Sort Algorithm in C#

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm that works by recursively dividing the array into two halves, sorting each half, and then merging them back together. The primary operation of the merge sort algorithm is the merge step, which combines two sorted halves into a single sorted array.

2. Implementation Steps

1. If the array has one or zero elements, it is already sorted. Return the array as is.

2. Divide the array into two halves.

3. Recursively sort both halves.

4. Merge the two halves together to produce a single sorted array.

3. Implementation in C#

using System;
public class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    public static void Merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        // Create temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];
        // Copy data to temp arrays L[] and R[]
        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];
        // Merge the temp arrays back into arr[l..r]
        int k = l;
        int x = 0, y = 0;
        while (x < n1 && y < n2) {
            if (L[x] <= R[y]) {
                arr[k] = L[x];
                x++;
            } else {
                arr[k] = R[y];
                y++;
            }
            k++;
        }
        // Copy the remaining elements of L[], if there are any
        while (x < n1) {
            arr[k] = L[x];
            x++;
            k++;
        }
        // Copy the remaining elements of R[], if there are any
        while (y < n2) {
            arr[k] = R[y];
            y++;
            k++;
        }
    }
    // Recursively sorts arr[l..r] using Merge()
    public static void Sort(int[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = l + (r - l) / 2;
            // Sort first and second halves
            Sort(arr, l, m);
            Sort(arr, m + 1, r);
            Merge(arr, l, m, r);
        }
    }
}
public class Program {
    public static void Main() {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        Console.WriteLine("Unsorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
        MergeSort.Sort(arr, 0, arr.Length - 1);
        Console.WriteLine("\nSorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
    }
}

Output:

Unsorted array:
38 27 43 3 9 82 10
Sorted array:
3 9 10 27 38 43 82

Explanation:

1. The MergeSort class has two primary methods: Merge and Sort.

2. The Merge method is responsible for merging two sorted halves of an array into a single sorted section. This is done by using two temporary arrays L and R which hold the two halves to be merged.

3. The Sort method is the recursive method that divides the array into two halves and sorts them. This division is done until arrays of size 1 or 0 are achieved, which are inherently sorted.

4. After both halves of a section are sorted, the Merge method is used to combine them into a single sorted section.

5. The Program class contains the Main method which showcases the sorting of an integer array using the MergeSort class. The unsorted and sorted arrays are displayed.