Merge sort program in C#

Merge sort is a divide-and-conquer sorting algorithm that works by recursively dividing the array into smaller subarrays, sorting them, and then merging them back together to obtain the final sorted array. It has a time complexity of O(n log n) and is a stable sorting algorithm, meaning it preserves the relative order of elements with equal values.

Here's an explanation of the merge sort algorithm step by step:

1. Divide: The array is divided into two halves, roughly equal in size. This process continues until each subarray has only one element (considered sorted).
2. Conquer: Merge sort recursively sorts each subarray by applying the merge sort algorithm to them.
3. Merge: The sorted subarrays are merged back together to form larger sorted subarrays. The merging process compares the elements from both subarrays and places them in the correct order in the merged array.
4. Repeat: Steps 2 and 3 are repeated until all subarrays have been merged, resulting in the final sorted array.

using System;

public class MergeSort
{
    public static void Main()
    {
        int[] arr = { 64, 25, 12, 22, 11 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr, 0, arr.Length - 1);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;

            // Sort first and second halves
            Sort(arr, left, middle);
            Sort(arr, middle + 1, right);

            // Merge the sorted halves
            Merge(arr, left, middle, right);
        }
    }

    public static void Merge(int[] arr, int left, int middle, int right)
    {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // Create temporary arrays
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++)
        {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++)
        {
            rightArr[j] = arr[middle + 1 + j];
        }

        // Merge the temporary arrays back into arr[]
        int k = left;
        int i = 0;
        int j = 0;

        while (i < n1 && j < n2)
        {
            if (leftArr[i] <= rightArr[j])
            {
                arr[k] = leftArr[i];
                i++;
            }
            else
            {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy the remaining elements of leftArr[], if any
        while (i < n1)
        {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        // Copy the remaining elements of rightArr[], if any
        while (j < n2)
        {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the merge sort algorithm, and the Merge method merges the sorted subarrays. The Main method initializes an array, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

The program demonstrates the step-by-step execution of the merge sort algorithm on the given array and outputs the sorted array.

Merge sort is a highly efficient sorting algorithm and is particularly useful when dealing with large datasets or external sorting where data does not fit entirely in memory.