Merge Sort Algorithm in DSA Java

Mental Model

Split the list into smaller parts, sort each part, then join them back 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 together in order.

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: We break the problem into smaller parts to sort easily

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 for easier sorting

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

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

Why: Single elements are sorted by default

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

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

Why: Prepare for merging sorted parts

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

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

Why: All parts are now single elements

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

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

Why: Combine sorted parts in order

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: Sort the last small parts

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

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

Why: Merge left half sorted

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

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

Why: Merge right half sorted

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 gives fully sorted list

Result:

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

Annotated Code

DSA Java

import java.util.Arrays;

public 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[] left = new int[n1];
        int[] right = new int[n2];

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

        int i = 0, j = 0, k = l;

        // Merge left and right arrays back into arr
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of left[], if any
        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }

        // Copy remaining elements of right[], if any
        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

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

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

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

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

if (l < r) {

Check if current subarray has more than one element to sort

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

Find middle index to split array

mergeSort(arr, l, m);

Recursively sort left half

mergeSort(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] = left[i]; i++;

Take element from left if smaller or equal

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

Take element from right if smaller

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

Copy remaining elements from left if any

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

Copy remaining elements from right if any

Output

[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 with O(n^2), merge sort is much faster for large lists due to divide and conquer

Edge Cases

Empty array

No sorting needed, function returns immediately

DSA Java

if (l < r) {

Single element array

Already sorted, no merge needed

DSA Java

if (l < r) {

Array with duplicate elements

Duplicates are kept and sorted correctly

DSA Java

if (left[i] <= right[j]) {

When to Use This Pattern

When you need to sort large lists efficiently and can split the problem into smaller parts, use merge sort because it guarantees O(n log n) time.

Common Mistakes

Mistake: Not copying remaining elements after merging main parts
Fix: Add loops to copy leftover elements from left or right subarrays after main merge loop

Mistake: Calculating middle index as (l + r) / 2 without considering overflow
Fix: Calculate middle as l + (r - l) / 2 to avoid integer overflow

Summary

It sorts a list by splitting it into halves, sorting each half, then merging them back in order.

Use it when you want a reliable, efficient sorting method especially for large lists.

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

Practice

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

easy

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

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

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

D. Build a heap and extract elements in sorted order

Solution

1. Step 1: Understand the divide and conquer approach

   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 to produce a fully sorted array.

3. Final Answer:

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

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 in place without merging
• Believing it picks smallest elements one by one

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

easy

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

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

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

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

Solution

1. Step 1: Identify parameters needed for merging

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

2. Step 2: Check return type and parameter order

   It returns nothing (void) and parameters match the signature in void merge(int[] arr, int left, int mid, int right).

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using wrong parameter order
• Returning int instead of void
• Missing mid index parameter

3. What will be the output of the following Java code snippet using Merge Sort on array {4, 1, 3, 2}?

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

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Understand mergeSort on {4,1,3,2}

   It splits into {4,1} and {3,2}, sorts each half to {1,4} and {2,3}.

2. Step 2: Merge sorted halves

   Merging {1,4} and {2,3} results in fully sorted array {1,2,3,4}.

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Confusing merge order
• Not sorting halves before merging
• Printing original unsorted array

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

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 + j];
  // merging logic follows...
}

medium

A. Array L should be of size n1 + 1

B. Lengths n1 and n2 should be mid - left + 1 and right - mid

C. Copying elements from arr to R should start from mid + 1

D. No bug, code is correct

Solution

1. Step 1: Check array lengths and copying ranges

   Lengths n1 = mid - left + 1 and n2 = right - mid are correct for the left half (left to mid) and right half (mid+1 to right).

2. Step 2: Verify copying elements to R array

   Copying to R starts at arr[mid], but it should start at arr[mid + 1] to avoid overlap.

3. Final Answer:

   Copying elements from arr to R should start from mid + 1 -> Option C

4. Quick Check:

   Right half copy starts at mid+1 [OK]

Hint: Right half starts copying from mid+1, not mid [OK]

Common Mistakes:

• Starting right half copy at mid instead of mid+1
• Incorrect array length calculation
• Assuming no overlap in copying

5. Given an array with many duplicate elements, how can you modify Merge Sort to maintain the original order of equal elements (stable sort)?

hard

A. When merging, always pick from the right subarray first

B. Merge Sort cannot be stable with duplicates

C. Use a hash map to track duplicates and reorder after sorting

D. When merging, if elements are equal, pick from the left subarray first

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in their original order.

2. Step 2: Modify merge step for stability

   When merging, if elements are equal, always choose the element from the left subarray first to preserve order.

3. Final Answer:

   When merging, if elements are equal, pick from the left subarray first -> Option D

4. Quick Check:

   Stable merge picks left element first on ties [OK]

Hint: Pick left element first when equal to keep order [OK]

Common Mistakes:

• Picking right element first breaks stability
• Thinking Merge Sort is unstable by default
• Using extra data structures unnecessarily