Merge Sort Algorithm in DSA C#

Mental Model

Split the list into smaller parts, sort each part, then join them back together in order.

Analogy: Imagine sorting a big pile of cards by splitting them into small piles, sorting each small pile, then carefully merging the piles back into one sorted stack.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split further:
[38] [27, 43]   [3, 9] [82, 10]

Sorted small parts:
[27, 38, 43]   [3, 9, 10, 82]

Merged sorted list:
[3, 9, 10, 27, 38, 43, 82]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split list into two halves

[38, 27, 43]   [3, 9, 82, 10]

Why: Splitting makes sorting smaller parts easier

Step 2: Split left half into [38] and [27, 43]

[38]   [27, 43]   [3, 9, 82, 10]

Why: Keep splitting until parts have one element

Step 3: Split right half into [3, 9] and [82, 10]

[38]   [27, 43]   [3, 9]   [82, 10]

Why: Continue splitting right half

Step 4: Split [27, 43] into [27] and [43]

[38]   [27]   [43]   [3, 9]   [82, 10]

Why: Split until single elements

Step 5: Split [3, 9] into [3] and [9]

[38]   [27]   [43]   [3]   [9]   [82, 10]

Why: Split right side further

Step 6: Split [82, 10] into [82] and [10]

[38]   [27]   [43]   [3]   [9]   [82]   [10]

Why: Final split to single elements

Step 7: Merge [27] and [43] into sorted [27, 43]

[38]   [27, 43]   [3]   [9]   [82]   [10]

Why: Merge small sorted parts

Step 8: Merge [3] and [9] into sorted [3, 9]

[38]   [27, 43]   [3, 9]   [82]   [10]

Why: Merge small sorted parts

Step 9: Merge [82] and [10] into sorted [10, 82]

[38]   [27, 43]   [3, 9]   [10, 82]

Why: Merge small sorted parts

Step 10: Merge [38] and [27, 43] into sorted [27, 38, 43]

[27, 38, 43]   [3, 9]   [10, 82]

Why: Merge sorted halves

Step 11: Merge [3, 9] and [10, 82] into sorted [3, 9, 10, 82]

[27, 38, 43]   [3, 9, 10, 82]

Why: Merge sorted halves

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into fully sorted list

[3, 9, 10, 27, 38, 43, 82]

Why: Final merge to get fully sorted list

Result:

[3, 9, 10, 27, 38, 43, 82]

Annotated Code

DSA C#

using System;

class MergeSort {
    // Merge two sorted subarrays arr[l..m] and arr[m+1..r]
    static void Merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];

        int iIndex = 0, jIndex = 0, k = l;

        while (iIndex < n1 && jIndex < n2) {
            if (L[iIndex] <= R[jIndex]) {
                arr[k] = L[iIndex];
                iIndex++;
            } else {
                arr[k] = R[jIndex];
                jIndex++;
            }
            k++;
        }

        while (iIndex < n1) {
            arr[k] = L[iIndex];
            iIndex++;
            k++;
        }

        while (jIndex < n2) {
            arr[k] = R[jIndex];
            jIndex++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using merge()
    static void Sort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            Sort(arr, l, m); // Sort first half
            Sort(arr, m + 1, r); // Sort second half

            Merge(arr, l, m, r); // Merge sorted halves
        }
    }

    static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i < arr.Length - 1) Console.Write(", ");
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr, 0, arr.Length - 1);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }
}

if (l < r) {

Check if the current subarray has more than one element to sort

int m = l + (r - l) / 2;

Find the middle index to split the array

Sort(arr, l, m); // Sort first half

Recursively sort the left half

Sort(arr, m + 1, r); // Sort second half

Recursively sort the right half

Merge(arr, l, m, r); // Merge sorted halves

Merge the two sorted halves into one sorted subarray

while (iIndex < n1 && jIndex < n2) {

Compare elements from left and right subarrays to merge in order

if (L[iIndex] <= R[jIndex]) {

Pick smaller element from left subarray

arr[k] = L[iIndex];

Place element into original array

iIndex++;

Move to next element in left subarray

else { arr[k] = R[jIndex]; jIndex++; }

Pick smaller element from right subarray and advance

k++;

Advance position in original array

while (iIndex < n1) { arr[k] = L[iIndex]; iIndex++; k++; }

Copy any remaining elements from left subarray

while (jIndex < n2) { arr[k] = R[jIndex]; jIndex++; k++; }

Copy any remaining elements from right subarray

Output

Original array:

38, 27, 43, 3, 9, 82, 10

Sorted array:

3, 9, 10, 27, 38, 43, 82

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because temporary arrays are used to hold elements during merging

vs Alternative: Compared to simple sorting like bubble sort (O(n^2)), merge sort is much faster for large lists but uses extra space

Edge Cases

Empty array

No sorting needed, function returns immediately

DSA C#

if (l < r) {

Single element array

Already sorted, no merge or further splits

DSA C#

if (l < r) {

Array with duplicate values

Duplicates are handled correctly and appear in sorted order

DSA C#

if (L[iIndex] <= R[jIndex]) {

When to Use This Pattern

When you need a reliable, fast sorting method that works well on large lists and can be implemented recursively, reach for merge sort because it splits and merges efficiently.

Common Mistakes

Mistake: Not splitting the array correctly causing infinite recursion
Fix: Ensure the base case 'if (l < r)' is checked before recursive calls

Mistake: Incorrectly merging arrays causing unsorted output
Fix: Carefully compare elements from both halves and copy remaining elements after main loop

Summary

It sorts a list by splitting it into halves, sorting each half, and merging them back together.

Use it when you want a fast, stable sort especially for large lists.

The key insight is breaking the problem into smaller sorted parts and merging them in order.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Pick the smallest element and place it at the beginning repeatedly

B. Divide the list into halves, sort each half, then merge them

C. Compare each element with every other element and swap if needed

D. Build a sorted list by inserting elements one by one

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into two halves recursively until each sublist has one element.

2. Step 2: Merge sorted halves

   Then it merges these small sorted lists back together in order to form a sorted list.

3. Final Answer:

   Divide the list into halves, sort each half, then merge them -> Option B

4. Quick Check:

   Merge Sort = Divide and conquer [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking it sorts by swapping adjacent elements
• Believing it sorts by inserting elements one by one

2. Which of the following is the correct way to declare the merge function header in C# for Merge Sort?

easy

A. void Merge(int[] arr, int left, int mid, int right)

B. int Merge(int arr[], int left, int mid, int right)

C. void merge(int arr[], int start, int end)

D. int merge(int[] arr, int left, int right)

Solution

1. Step 1: Identify correct parameter types and names

   The merge function typically takes the array and three indices: left, mid, and right to merge two sorted halves.

2. Step 2: Check C# syntax for method declaration

   In C#, arrays are declared as int[] arr and the function returns void because it modifies the array in place.

3. Final Answer:

   void Merge(int[] arr, int left, int mid, int right) -> Option A

4. Quick Check:

   Correct signature = void Merge(int[] arr, int left, int mid, int right) [OK]

Hint: Look for void return and correct parameters [OK]

Common Mistakes:

• Using incorrect return type (int instead of void)
• Wrong parameter types or order
• Using lowercase function names in C#

3. What will be the output of the following C# code snippet using Merge Sort on array [4, 1, 3, 2]?

int[] arr = {4, 1, 3, 2};
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(", ", arr));

medium

A. 1, 3, 2, 4

B. 4, 3, 2, 1

C. 1, 2, 3, 4

D. 2, 1, 3, 4

Solution

1. Step 1: Apply Merge Sort to the array [4, 1, 3, 2]

   Split into [4,1] and [3,2], sort each half to [1,4] and [2,3].

2. Step 2: Merge the two sorted halves

   Merging [1,4] and [2,3] results in [1, 2, 3, 4].

3. Final Answer:

   1, 2, 3, 4 -> Option C

4. Quick Check:

   Sorted array = 1, 2, 3, 4 [OK]

Hint: Merge halves stepwise to get sorted array [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting array correctly
• Printing before sorting completes

4. Identify the bug in this Merge Sort merge function snippet:

void Merge(int[] arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int[] L = new int[n1];
  int[] R = new int[n2];
  for (int i = 0; i < n1; i++) L[i] = arr[left + i];
  for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
  // merging logic follows
}

medium

A. Incorrect array sizes for L and R

B. Loop conditions should use < instead of <= to avoid out of bounds

C. Wrong indices used for copying elements

D. Missing return statement in void function

Solution

1. Step 1: Check array size calculations

   The size of the left array should be mid - left + 1 to include the mid element; the right array size is correct as right - mid.

2. Step 2: Analyze loop conditions for copying elements

   Loops should use < to avoid out of bounds errors.

3. Final Answer:

   Incorrect array sizes for L and R -> Option A

4. Quick Check:

   Left array size must be mid - left + 1 [OK]

Hint: Array size for left = mid - left + 1 [OK]

Common Mistakes:

• Using <= causes index out of range errors
• Miscalculating array sizes
• Confusing mid index offsets

5. Given a large dataset with many duplicate values, how can you modify the Merge Sort algorithm to maintain stability (keep duplicates in original order)?

hard

A. Change Merge Sort to Quick Sort for better stability

B. Sort duplicates separately after Merge Sort completes

C. Use a hash set to remove duplicates before sorting

D. When merging, if elements are equal, take element from left subarray first

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in the same order as original.

2. Step 2: Modify merge step to preserve order

   When merging, if elements are equal, always pick from the left subarray first to keep original order.

3. Final Answer:

   When merging, if elements are equal, take element from left subarray first -> Option D

4. Quick Check:

   Stable merge = pick left element first on ties [OK]

Hint: Pick left element first when equal during merge [OK]

Common Mistakes:

• Removing duplicates before sorting changes data
• Assuming Quick Sort is stable (it is not)
• Sorting duplicates separately after merge