Merge Sort as Divide and Conquer in DSA Java

Mental Model

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

Analogy: Imagine sorting a messy pile of papers by first dividing them into smaller piles, sorting each small pile, then stacking the sorted piles together neatly.

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

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

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

Keep splitting until single elements:
[38] [27] [43]   [3] [9] [82] [10]

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using merge sort

Step 1: Split array into two halves

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

Why: Divide the problem into smaller parts to make sorting easier

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

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

Why: Keep dividing until subarrays have one element

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

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

Why: Single elements are considered sorted

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

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

Why: Combine sorted subarrays into bigger sorted arrays

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

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

Why: Continue merging sorted parts

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

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

Why: Divide right half to sort smaller parts

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

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

Why: Single elements are sorted

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

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

Why: Merge sorted elements

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

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

Why: Divide until single elements

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

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

Why: Merge sorted elements

Step 11: Merge [3, 9] and [10, 82] into [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 [3, 9, 10, 27, 38, 43, 82]

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

Why: Final merge to get fully sorted array

Result:

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

Annotated Code

DSA Java

public class MergeSort {

    // Merge two sorted subarrays arr[l..m] and arr[m+1..r]
    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 i = 0, j = 0;
        int k = l;

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

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

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

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

            sort(arr, l, m); // sort left half
            sort(arr, m + 1, r); // sort right half

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

    // Utility function to print array
    static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i != arr.length - 1) System.out.print(", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        MergeSort ms = new MergeSort();
        ms.sort(arr, 0, arr.length - 1);

        printArray(arr);
    }
}

if (l < r) {

check if subarray has more than one element to continue dividing

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

find middle index to split array

sort(arr, l, m);

recursively sort left half

sort(arr, m + 1, r);

recursively sort right half

merge(arr, l, m, r);

merge two sorted halves into one sorted array

while (i < n1 && j < n2) {

compare elements from left and right subarrays to merge in order

arr[k] = L[i]; i++;

copy smaller element from left subarray

arr[k] = R[j]; j++;

copy smaller element from right subarray

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

copy remaining elements from left subarray if any

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

copy remaining elements from right subarray if any

Output

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

Complexity Analysis

Time: O(n log n) because the array 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 arrays due to divide and conquer approach

Edge Cases

empty array

function returns immediately without changes

DSA Java

if (l < r) {

array with one element

already sorted, no merge needed

DSA Java

if (l < r) {

array with duplicate elements

duplicates are kept and sorted correctly

DSA Java

if (L[i] <= R[j]) {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially large lists, reach for merge sort because it splits the problem into smaller parts and merges them sorted.

Common Mistakes

Mistake: Not handling the base case correctly, causing infinite recursion
Fix: Add condition to stop recursion when subarray has one or zero elements: if (l < r)

Mistake: Merging without copying remaining elements from left or right subarray
Fix: Add loops to copy leftover elements after main merge loop

Mistake: Calculating middle index incorrectly causing overflow
Fix: Use int m = l + (r - l) / 2 instead of (l + r) / 2

Summary

It sorts an array by dividing it into halves, sorting each half, and merging them back.

Use it when you need a reliable, efficient sorting method for large data.

The key insight is breaking a big problem into smaller sorted pieces and combining them.

Practice

1. What is the main idea behind the Merge Sort algorithm in the context of divide and conquer?

easy

A. Select a pivot and partition the array around it

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into halves, sort each half, then merge them

D. Build a heap and extract elements in sorted order

Solution

1. Step 1: Understand divide and conquer in Merge Sort

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   It then merges these sorted halves back together to form a sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option C

4. Quick Check:

   Divide and conquer = split, sort, merge [OK]

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

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses pivot like Quick Sort
• Ignoring the merge step after dividing

2. Which of the following is the correct way to declare the merge function header in Java for merging two sorted subarrays in Merge Sort?

easy

A. int merge(int arr[], int start, int end)

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

C. void merge(int arr[], int low, int high)

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

Solution

1. Step 1: Identify parameters needed for merging

   The merge function needs the array and indices: left, mid, right to merge two halves.

2. Step 2: Check method signature correctness

   It returns void and takes int[] arr, int left, int mid, int right as parameters.

3. Final Answer:

   void merge(int[] arr, int left, int mid, int right) -> Option B

4. Quick Check:

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

Hint: Merge needs array and three indices: left, mid, right [OK]

Common Mistakes:

• Using wrong parameter names or missing mid index
• Returning int instead of void
• Confusing start/end with left/right without mid

3. What will be the output of the following Java code snippet using Merge Sort on the array [4, 1, 3, 9, 7]?

int[] arr = {4, 1, 3, 9, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));

medium

A. [1, 4, 3, 7, 9]

B. [4, 1, 3, 7, 9]

C. [9, 7, 4, 3, 1]

D. [1, 3, 4, 7, 9]

Solution

1. Step 1: Apply Merge Sort to the array

   Merge Sort divides and merges to sort: [4,1,3,9,7] -> [1,3,4,7,9]

2. Step 2: Verify final sorted array

   The sorted array is ascending: [1, 3, 4, 7, 9]

3. Final Answer:

   [1, 3, 4, 7, 9] -> Option D

4. Quick Check:

   Sorted array = ascending order [OK]

Hint: Merge Sort always outputs sorted ascending array [OK]

Common Mistakes:

• Confusing merge step output with partial arrays
• Assuming original order remains
• Mixing up ascending and descending order

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

void merge(int[] arr, int left, int mid, int right) {
  int n1 = mid - left;
  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 calculation of n1 size

B. Wrong copying of elements into R array

C. Missing return statement in void method

D. Using < instead of <= in for loops

Solution

1. Step 1: Check size calculations for subarrays

   n1 should be mid - left + 1 and n2 should be right - mid to cover all elements.

2. Step 2: Identify impact of wrong sizes

   Incorrect sizes cause array index errors or missing elements during merge.

3. Final Answer:

   Incorrect calculation of n1 size -> Option A

4. Quick Check:

   Sizes must include mid element [OK]

Hint: Remember: n1 = mid-left+1, n2 = right-mid [OK]

Common Mistakes:

• Forgetting +1 in n1 size calculation
• Copying elements starting at wrong index
• Confusing loop bounds with <= instead of <

5. Given an array with many duplicate values, how should the merge step in Merge Sort be adapted to maintain stability (preserve original order of equal elements)?

hard

A. When elements are equal, copy from the left subarray first

B. When elements are equal, copy from the right subarray first

C. Skip duplicates during merge to reduce array size

D. Sort duplicates separately after merge

Solution

1. Step 1: Understand stability in sorting

   Stable sort keeps equal elements in original order.

2. Step 2: Apply stability rule in merge step

   When equal, copy element from left subarray first to preserve order.

3. Final Answer:

   When elements are equal, copy from the left subarray first -> Option A

4. Quick Check:

   Left first on equals = stable merge [OK]

Hint: Copy left element first on equal values to keep stability [OK]

Common Mistakes:

• Copying right element first breaks stability
• Removing duplicates during merge
• Sorting duplicates separately after merge