Merge Sort Algorithm 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 implementation 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 time complexity of merge sort

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

A O(n^2)

B O(log n)

C O(n log n)

D O(n)

💡 Hint

Consider how many times the list is split and merged.

Merge sort splits the list into halves (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time complexity.

🔧 Debug

advanced

Identify the error in this merge function

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

DSA Python

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

A No error, returns correct merged list

B TypeError because of wrong comparison

C Infinite loop because i and j never increment

D IndexError due to accessing out of range index

💡 Hint

Check the loop condition and how indices i and j are used.

The loop uses 'or' which allows i or j to go out of range. Accessing left[i] or right[j] when i or j is beyond list length causes IndexError.

🚀 Application

advanced

Using merge sort to count inversions

How can merge sort be modified to count the number of inversions (pairs where a larger number appears before a smaller one) in a list?

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

B Count inversions by comparing every pair after sorting

C Count inversions only in the base case when list size is 1

D Count inversions by summing lengths of left and right lists

💡 Hint

Think about when elements from the right half are merged before left half elements.

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

📝 Syntax

expert

Identify the syntax error in this merge sort code snippet

Which option correctly identifies the syntax error in this merge sort snippet?

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)

A Using '//' instead of '/' for division

B Missing colon ':' after if condition

C Incorrect indentation of return statement

D Missing parentheses in function call merge_sort

💡 Hint

Check the if statement syntax carefully.

The if statement is missing a colon ':' at the end of the condition line, causing a syntax error.

Practice

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

easy

A. Swap adjacent elements repeatedly until sorted

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

C. Pick the smallest element and move it to the front repeatedly

D. Build a sorted list by inserting elements one by one

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to make sorting easier.

2. Step 2: Merge sorted halves

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

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking it swaps elements directly without splitting
• Assuming it sorts in one pass

2. Which of the following is the correct way to split a list arr into two halves in Python for merge sort?

easy

A. left = arr[:len(arr)//2+1]; right = arr[len(arr)//2:]

B. left = arr[1:len(arr)//2]; right = arr[len(arr)//2+1:]

C. left = arr[:len(arr)//2]; right = arr[len(arr)//2:]

D. left = arr[:len(arr)/2]; right = arr[len(arr)/2:]

Solution

1. Step 1: Use integer division for slicing

   Python list slicing requires integer indices; len(arr)//2 gives an integer midpoint.

2. Step 2: Slice correctly for left and right halves

   Left half is from start to midpoint (exclusive), right half from midpoint to end.

3. Final Answer:

   left = arr[:len(arr)//2]; right = arr[len(arr)//2:] -> Option C

4. Quick Check:

   Integer division and slicing = left = arr[:len(arr)//2]; right = arr[len(arr)//2:] [OK]

Hint: Use // for integer division in slicing [OK]

Common Mistakes:

• Using single slash / causing float index error
• Incorrect slice ranges skipping elements
• Adding +1 unnecessarily in slicing

3. What will be the output of the following code snippet?

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, 3, 4]

Solution

1. Step 1: Recursively split and sort the list

   The list [4,1,3,2] is split into [4,1] and [3,2], then further until single elements.

2. Step 2: Merge sorted halves step-by-step

   Merge [4] and [1] to get [1,4], merge [3] and [2] to get [2,3], then merge [1,4] and [2,3] to get [1,2,3,4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Trace splits and merges carefully [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Not extending remaining elements after main loop
• Mixing up indices i and j

4. Identify the error in this merge function used in merge sort:

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

medium

A. Using 'or' instead of 'and' in while condition causes index errors

B. Missing initialization of result list

C. Appending elements without comparing

D. Not returning the merged list

Solution

1. Step 1: Analyze the while loop condition

   Using 'or' means loop continues even if one list is exhausted, causing index out of range errors.

2. Step 2: Correct condition and handle leftovers

   The condition should be 'and' to compare elements safely, then extend remaining elements after loop.

3. Final Answer:

   Using 'or' instead of 'and' in while condition causes index errors -> Option A

4. Quick Check:

   While condition must be 'and' to avoid errors [OK]

Hint: Use 'and' in loop to avoid index errors [OK]

Common Mistakes:

• Using 'or' causing index out of range
• Not extending leftover elements after loop
• Forgetting to increment indices properly

5. You want to sort a list of tuples [(3, 'c'), (1, 'a'), (2, 'b')] by the first element using merge sort. Which modification is needed in the merge function's comparison?

hard

A. Compare using if left[i][1] < right[j][1]:

B. Use if left[i] < right[j]: without change

C. Convert tuples to strings before comparing

D. Change comparison to if left[i][0] < right[j][0]:

Solution

1. Step 1: Understand tuple comparison

   Tuples compare element-wise, but to sort by first element explicitly, compare left[i][0] and right[j][0].

2. Step 2: Modify merge comparison accordingly

   Change the if condition in merge to compare the first elements of tuples for correct sorting.

3. Final Answer:

   Change comparison to if left[i][0] < right[j][0]: -> Option D

4. Quick Check:

   Compare tuple first elements for sorting [OK]

Hint: Compare tuple elements explicitly by index [OK]

Common Mistakes:

• Comparing whole tuples without index may work but is unclear
• Comparing second element instead of first
• Converting tuples to strings unnecessarily