private static void Merge(int[] array, int start, int mid, int end)
{
    int left = start;
    int right = mid + 1;
    int[] temp = new int[end - start + 1];
    int index = 0;
    while (left <= mid && right <= end)
    {
        if (array[left] <= array[right])
        {
            temp[index] = array[left];
            left++;
        }
        else        {
            temp[index] = array[right];
            right++;
        }
        index++;
    }
    while (left <= mid)
    {
        temp[index] = array[left];
        left++;
        index++;
    }
    while (right <= end)
    {
        temp[index] = array[right];
        right++;
        index++;
    }
    for (int i = start; i <= end; i++)
    {
        array[i] = temp[i - start];
    }
}