Merge Sort as Divide and Conquer in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the list into two halves.

DSA Python

mid = len(arr) [1] 2

Drag options to blanks, or click blank then click option'

A*

B+

C-

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using '/' instead of '//' causes a float index error.

Using '+' or '-' changes the index incorrectly.

We use integer division (//) to find the middle index so that it is an integer.

2fill in blank

medium

Complete the code to recursively sort the left half of the list.

DSA Python

left_sorted = merge_sort(arr[1]:mid)

Drag options to blanks, or click blank then click option'

A[

B(

C<

D{

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses () instead of brackets [] causes a syntax error.

Using curly braces {} is for sets or dictionaries, not slicing.

We use square brackets [] to slice the list from start to mid.

3fill in blank

hard

Fix the error in the merge step to compare elements correctly.

DSA Python

if left[i] [1] right[j]:

Drag options to blanks, or click blank then click option'

A>

B==

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' reverses the order and breaks sorting.

Using '==' or '!=' does not help in ordering.

We compare if left[i] is less than right[j] to merge in sorted order.

4fill in blank

hard

Fill both blanks to complete the loop that merges remaining elements.

DSA Python

while i [1] len(left):
    result.append(left[2])
    i += 1

Drag options to blanks, or click blank then click option'

A<

B[i]

C>

D(i)

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' causes the loop to never run or run incorrectly.

Using parentheses instead of brackets causes errors.

The loop runs while i is less than the length of left, and we append left[i].

5fill in blank

hard

Fill all three blanks to complete the merge function's return statement.

DSA Python

return result + left[1] + right[2] if i [3] len(left) else result + right[j:]

Drag options to blanks, or click blank then click option'

A[i:]

B[j:]

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' reverses the condition and breaks logic.

Using wrong slice indices causes errors.

We add the remaining elements from left[i:] and right[j:] if i is less than len(left), else result + right[j:].

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)