using System;

using System.Linq;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        MergeSort();

    }

​

    public static void MergeSort()

    {

        var nums = new int[]{3, 1, 2, 3, 6, 5,123,52,1,23,124,15,62,3,423,4,23,42,12,3,123};

        Sort(nums);

        foreach (var num in nums)

        {

            Console.WriteLine(num);

        }

    }

​

    private static void Sort(int[] arr)

    {

        if (arr.Length < 2)

        {

            return;

        }

​

        // swap elements

        if (arr.Length == 2 && arr[0] > arr[1])

        {

            var temp = arr[1];

            arr[1] = arr[0];

            arr[0] = temp;

            return;

        }

​

        var leftSize = arr.Length / 2;

        var rightSize = arr.Length - leftSize;

        var leftArr = new int[leftSize];

        var rightArr = new int[rightSize];

        for (int i = 0; i < arr.Length; i++)

        {

            if (i < leftSize)

            {

                leftArr[i] = arr[i];

            }

            else

            {

                rightArr[i - leftSize] = arr[i];

            }

        }

​

        Sort(leftArr);

        Sort(rightArr);

        Merge(leftArr, rightArr, arr);

    }

​

    private static void Merge(int[] leftArr, int[] rightArr, int[] parentArr)

    {

        int leftIndex = 0;

        var rightIndex = 0;

        var parentIndex = 0;

        while (leftIndex < leftArr.Length && rightIndex < rightArr.Length)

        {

            if (leftArr[leftIndex] <= rightArr[rightIndex])

            {

                parentArr[parentIndex] = leftArr[leftIndex++];

            }

            else

            {

                parentArr[parentIndex] = rightArr[rightIndex++];

            }

​

            parentIndex++;

        }

​

        while (rightIndex < rightArr.Length)

        {

            parentArr[parentIndex] = rightArr[rightIndex];

            rightIndex++;

            parentIndex++;

        }

​

        while (leftIndex < leftArr.Length)

        {

            parentArr[parentIndex] = leftArr[leftIndex];

            leftIndex++;

            parentIndex++;

        }

    }

}