Merge Sort Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the output of the following Java code after sorting the array using merge sort?

DSA Java

public class MergeSortTest {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static 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];

        int i = 0, j = 0, k = left;
        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++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

A 2 3 4 5 8

B 8 5 4 3 2

C 5 3 8 4 2

D 2 4 3 5 8

💡 Hint

Trace the merge steps carefully, the array is sorted in ascending order.

The merge sort algorithm divides the array into halves recursively and merges them back in sorted order. The final output is the sorted array: 2 3 4 5 8.

🧠 Conceptual

intermediate

Understanding Merge Sort Time Complexity

What is the time complexity of merge sort in the average and worst cases?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

💡 Hint

Think about how many times the array is split and merged.

Merge sort divides the array into halves log n times and merges n elements each time, resulting in O(n log n) time complexity.

🔧 Debug

advanced

Identify the bug in this merge function

What error will occur when running this merge function in merge sort?

DSA Java

public static 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];

    int i = 0, j = 0, k = left;
    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++;
    }
}

A No error, runs correctly

B NullPointerException

C ArrayIndexOutOfBoundsException

D Infinite loop

💡 Hint

Check the loop conditions for copying elements into L array.

The for loop copying elements into L uses i <= n1 which goes out of bounds. It should be i < n1.

🚀 Application

advanced

Using Merge Sort to count inversions

How can merge sort be modified to count the number of inversions (pairs where a[i] > a[j] and i < j) in an array?

A Count inversions only in the left half recursively

B Count inversions during the merge step when elements from right array are placed before left array elements

C Count inversions by comparing all pairs after sorting

D Count inversions only in the right half recursively

💡 Hint

Think about when elements from the right half are smaller than those in the left half during merging.

During merge, when an element from the right half is placed before elements in the left half, it indicates inversions equal to the remaining elements in left half.

📝 Syntax

expert

Identify the syntax error in this merge sort snippet

Which option correctly fixes the syntax error in this code snippet?

DSA Java

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

A Remove the merge call

B Change if (left < right) to if left < right:

C Replace mergeSort calls with merge_sort calls

D Add a semicolon after int mid = (left + right) / 2;

💡 Hint

Look carefully at the line declaring mid.

Java requires a semicolon at the end of statements. Missing semicolon causes syntax error.

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