Understanding Merge Sort and Merging Two Sorted Arrays in C#

The merge sort algorithm follows the divide‑and‑conquer paradigm: a large problem is recursively split into smaller sub‑problems, each solved independently, and then the solutions are merged to form the final sorted result.

Because the recursion forms a complete binary tree, the algorithm performs log₂ n levels of merging, each level processing O(n) elements, resulting in an overall time complexity of O(n log n). Merge sort uses extra memory for the temporary array but offers stable and efficient sorting.

Below is a full C# implementation of a generic merge sort, including the recursive Sort method and a Main entry that demonstrates sorting an integer array.

static void Main(string[] args)
{
    int[] arr = new int[] { 14,12,15,13,11,16 ,10};
    int[] newArr = Sort(arr, new int[7], 0, arr.Length - 1);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }
    Console.ReadKey();
}
public static int[] Sort(int[] arr, int[] result, int start, int end)
{
    if (start >= end)
        return null;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    Sort(arr, result, start1, end1);
    Sort(arr, result, start2, end2);
    int k = start;
    //进行比较。注意这里++是后执行的，先取出来数组中的值然后++
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    //将每个分组剩余的进行复制
    while (start1 <= end1)
        result[k++] = arr[start1++];
    //将每个分组剩余的进行复制
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
    return result;
}

The original problem asks to merge two already sorted arrays. Using the same merge‑step logic, we can combine the two sequences without performing a full sort.

The following C# program merges two sorted arrays arr1 and arr2 into a new sorted array, illustrating the pointer movement with blue and red arrows in the accompanying diagrams.

static void Main(string[] args)
{
    int[] arr1 = new int[] { 2, 3, 6, 8 };
    int[] arr2 = new int[] { 1, 4, 5, 7 };
    int[] newArr = Sort(arr1, arr2);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }
    Console.ReadKey();
}
public static int[] Sort(int[] arr1,int[] arr2)
{
    int[] newArr = new int[arr1.Length + arr2.Length];
    int i = 0, j = 0, k = 0;
    while (i < arr1.Length && j < arr2.Length)
    {
        if (arr1[i] < arr2[j])
        {
            newArr[k] = arr1[i];
            i++;
            k++;
        }
        else
        {
            newArr[k] = arr2[j];
            j++;
            k++;
        }
    }
    while (i < arr1.Length)
        newArr[k++] = arr1[i++];
    while (j < arr2.Length)
        newArr[j++] = arr2[j++];
    return newArr;
}

Both code samples demonstrate how merge sort’s core idea—splitting, sorting, and merging—can be applied directly to combine pre‑sorted sequences efficiently.