Merge Sort as Divide and Conquer 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 performing merge sort on the array?

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++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

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

A 1 2 5 5 9

B 5 2 9 1 5

C 9 5 5 2 1

D 1 5 2 5 9

💡 Hint

Remember that merge sort divides the array and merges sorted halves.

Merge sort divides the array into halves recursively and merges them in sorted order. The final sorted array is 1 2 5 5 9.

🧠 Conceptual

intermediate

Understanding the divide step in merge sort

In merge sort, what is the main purpose of the divide step?

A To swap elements to sort the array in place

B To merge two sorted arrays into one sorted array

C To find the maximum element in the array

D To split the array into smaller parts until each part has one element

💡 Hint

Think about how merge sort breaks down the problem.

The divide step breaks the array into smaller parts until each part has only one element, which is naturally sorted.

🔧 Debug

advanced

Identify the error 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++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

A ArrayIndexOutOfBoundsException due to for loop condition i <= n1

B Infinite loop in while merging because i and j are never incremented

C No error, code runs correctly

D NullPointerException because arrays L and R are not initialized

💡 Hint

Check the for loop that copies elements into L array.

The for loop uses i <= n1 which goes out of bounds since arrays are 0-indexed and length is n1.

🚀 Application

advanced

Number of comparisons in merge sort

What is the approximate number of comparisons merge sort makes when sorting an array of size n?

A O(n^2)

B O(n log n)

C O(log n)

D O(n)

💡 Hint

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

Merge sort divides the array log n times and does n comparisons per level, resulting in O(n log n) comparisons.

❓ Predict Output

expert

Output after partial merge sort steps

Given the array {8, 3, 7, 4} and the following partial merge sort steps, what is the array after merging the first two elements and the last two elements separately?

DSA Java

int[] arr = {8, 3, 7, 4};
// After splitting into two halves: {8, 3} and {7, 4}
// After sorting each half separately:
// First half sorted: {3, 8}
// Second half sorted: {4, 7}
// What is the array after these partial steps (before final merge)?
// The array is updated in place.

A [3, 4, 7, 8]

B [8, 3, 7, 4]

C [3, 8, 4, 7]

D [4, 3, 8, 7]

💡 Hint

After sorting halves, each half is sorted but not merged together yet.

Each half is sorted individually, so first half becomes 3,8 and second half 4,7. The array is [3,8,4,7] before final merge.

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