using System;

public class Program

{

    public static void Main()

    {

        int[] array = { 3, 7, 12, 14, 2, 6, 9 };

        MergeSort(array, 0, array.Length-1);

        Console.WriteLine("Array after sorting: " + string.Join(", ", array));

    }

    static void MergeSort(int[] array, int p, int r)

    {

        // Recursive case

        if(p < r)

        {

            int q = (p + r) / 2;

            MergeSort(array, p, q);

            MergeSort(array, q + 1, r);

            Merge(array, p, q, r);

        }

    }

    static void Merge(int[] array, int p, int q, int r)

    {

​

        int[] lowHalf = new int[q-p+1];

        int[] highHalf = new int[r-q];

        int k = p;

        int i = 0;

        int j = 0;

        for(i = 0; i < lowHalf.Length; i++, k++)

        {

            lowHalf[i] = array[k];

        }

        for(j = 0; j < highHalf.Length; j++, k++)

        {

            highHalf[j] = array[k];

        }

        k = p;

        i = 0;

        j = 0;

        while(i < lowHalf.Length && j < highHalf.Length)

        {

            if(lowHalf[i] < highHalf[j])

            {

                array[k] = lowHalf[i];

                i++;

            }

            else

            {

                array[k] = highHalf[j];

                j++;

            }

            k++;

        }

        while(i < lowHalf.Length)

        {

            array[k] = lowHalf[i];

            i++;

            k++;

        }

        while(j < highHalf.Length)

        {

            array[k] = highHalf[j];

            j++;

            k++;

        }

    }

}