Merge sort

Merge sort - an array sorting algorithm that is implemented on the principle of “divide and conquer”. The task of sorting an array is divided into several sub-tasks of sorting arrays of smaller size, after which the result is combined, which leads to the solution of the initial problem.

Description of the merge sort algorithm

The merge sort algorithm is as follows:

• The input array is divided into two parts of the same size;
• Each of the subarrays is sorted separately, according to the same principle, that is, repeated breaking is performed until the length of the subarray reaches unity. In this case, each unit array is considered sorted;
• After this, all subarrays are merged into one, as a result of which we get sorted data.

Implement merge sort

using System;

class program
{
    // method for merging arrays
    static void Merge(int[] array, int lowIndex, int middleIndex, int highIndex)
    {
        var left = lowIndex;
        var right = middleIndex + 1;
        var tempArray = new int[highIndex - lowIndex + 1];
        var index = 0;

        while ((left <= middleIndex) && (right <= highIndex))
        {
            if (array[left] < array[right])
            {
                tempArray[index] = array[left];
                left++;
            }
            else
            {
                tempArray[index] = array[right];
                right++;
            }

            index++;
        }

        for (var i = left; i <= middleIndex; i++)
        {
            tempArray[index] = array[i];
            index++;
        }

        for (var i = right; i <= highIndex; i++)
        {
            tempArray[index] = array[i];
            index++;
        }

        for (var i = 0; i < tempArray.Length; i++)
        {
            array[lowIndex + i] = tempArray[i];
        }
    }

    // merge sort
    static int[] MergeSort(int[] array, int lowIndex, int highIndex)
    {
        if (lowIndex < highIndex)
        {
            var middleIndex = (lowIndex + highIndex) / 2;
            MergeSort(array, lowIndex, middleIndex);
            MergeSort(array, middleIndex + 1, highIndex);
            Merge(array, lowIndex, middleIndex, highIndex);
        }

        return array;
    }

    static int[] MergeSort(int[] array)
    {
        return MergeSort(array, 0, array.Length - 1);
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Merge Sort");
        Console.Write("Enter elements of the array:");
        var s = Console.ReadLine().Split(new[] { "", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
        var array = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            array[i] = Convert.ToInt32(s[i]);
        }

        Console.WriteLine("Ordered array: {0}", string.Join(",", MergeSort(array)));

        Console.ReadLine();
    }
}

The result of the program: