Merge Sort as Divide and Conquer in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small list

What is the output of the following merge sort code when sorting the list [4, 1, 3, 2]?

DSA Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([4, 1, 3, 2]))

A [1, 2, 3, 4]

B [4, 3, 2, 1]

C [1, 3, 2, 4]

D [2, 1, 3, 4]

💡 Hint

Think about how merge sort splits the list and merges sorted halves.

Merge sort splits the list into halves recursively until single elements remain, then merges them back in sorted order. The final output is the sorted list [1, 2, 3, 4].

🧠 Conceptual

intermediate

Understanding the divide step in merge sort

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

A To split the list into smaller parts until each part has one element

B To merge two sorted lists into one sorted list

C To swap elements to sort the list in place

D To find the largest element in the list

💡 Hint

Divide step breaks the problem into smaller pieces.

The divide step splits the list into smaller parts until each part has only one element, which is the base case for merge sort.

❓ Predict Output

advanced

Output of merge function with overlapping elements

What is the output of the merge function when merging these two sorted lists: [1, 3, 5] and [2, 3, 4]?

DSA Python

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([1, 3, 5], [2, 3, 4]))

A [1, 3, 5, 2, 3, 4]

B [1, 2, 3, 3, 4, 5]

C [1, 2, 3, 4, 5]

D [2, 3, 4, 1, 3, 5]

💡 Hint

The merge function combines two sorted lists into one sorted list, including duplicates.

The merge function compares elements from both lists and appends the smaller one, preserving duplicates and order, resulting in [1, 2, 3, 3, 4, 5].

🔧 Debug

advanced

Identify the error in this merge sort implementation

What error will this merge sort code produce when run on []?

DSA Python

def merge_sort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([]))

A TypeError because of wrong data type

B IndexError due to out of range access

C RecursionError due to infinite recursion

D [1, 2, 3] output correctly

💡 Hint

Check the base case condition for recursion termination.

The base case checks if length is exactly 1, but for empty lists it recurses infinitely causing RecursionError.

🚀 Application

expert

Number of merge operations in merge sort

For a list of 8 elements, how many times is the merge function called during the entire merge sort process?

A 16

B 8

C 15

D 7

💡 Hint

Think about how many merges happen at each level of splitting.

Merge sort splits the list into single elements and merges back. For 8 elements, merge is called 7 times (one less than number of elements).

Practice

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

easy

A. Insert elements one by one into a sorted list

B. Sort the list by repeatedly swapping adjacent elements

C. Select a pivot and partition the list around it

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

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to simplify sorting.

2. Step 2: Merge sorted halves

   After sorting each half, it merges them to form a sorted list.

3. Final Answer:

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

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 merge sort sorts in place without merging
• Mixing merge sort with quicksort pivot method

2. Which of the following is the correct base case condition in a recursive merge sort function in Python?

easy

A. if len(arr) > 1: return arr

B. if len(arr) <= 1: return arr

C. if arr is None: return []

D. if len(arr) == 0: return None

Solution

1. Step 1: Identify when recursion should stop

   Merge sort stops splitting when the list has 1 or 0 elements.

2. Step 2: Correct base case condition

   Checking if length is less than or equal to 1 returns the list as is.

3. Final Answer:

   if len(arr) <= 1: return arr -> Option B

4. Quick Check:

   Base case = list size ≤ 1 [OK]

Hint: Base case: list with 0 or 1 element is already sorted [OK]

Common Mistakes:

• Using wrong base case like len(arr) == 0 only
• Returning None instead of the list
• Incorrect condition that never stops recursion

3. What is the output of the following code?

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([4, 1, 3, 2]))

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 4, 3]

Solution

1. Step 1: Trace recursive splitting

   List splits into [4,1] and [3,2], then further splits until single elements.

2. Step 2: Merge sorted halves

   Merge combines sorted lists step-by-step to form [1,2,3,4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort always returns sorted list ascending [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to extend remaining elements after loop
• Mixing up indices i and j in merge

4. Find the error in this merge sort implementation:

def merge_sort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

medium

A. Base case should be len(arr) <= 1, not len(arr) == 1

B. Merge function should use <= instead of < in comparison

C. Indices i and j should start at 1, not 0

D. Should return arr before checking base case

Solution

1. Step 1: Check base case condition

   Base case only handles lists of length 1, but empty lists cause infinite recursion.

2. Step 2: Correct base case to include empty list

   Change condition to len(arr) <= 1 to handle empty and single element lists.

3. Final Answer:

   Base case should be len(arr) <= 1, not len(arr) == 1 -> Option A

4. Quick Check:

   Base case must handle empty or single element [OK]

Hint: Base case must cover empty and single element lists [OK]

Common Mistakes:

• Using strict equality for base case
• Starting indices at 1 causing index errors
• Changing comparison operator unnecessarily

5. Given a list of 8 elements, how many times will the merge function be called during a full merge sort?

hard

A. 8

B. 15

C. 7

D. 16

Solution

1. Step 1: Understand merge calls in merge sort

   Merge is called once for each internal node in the recursion tree (combining two sorted sublists).

2. Step 2: Calculate number of merge calls for 8 elements

   4 merges (size 2 sublists) + 2 merges (size 4) + 1 merge (size 8) = 7 total. Formula: n - 1 = 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Merge calls = n - 1 = 7 [OK]

Hint: Total merges in merge sort = n - 1 [OK]

Common Mistakes:

• Counting only top-level merges
• Confusing merges with splits
• Using 2n-1 (confusing with total recursive calls to merge_sort)