Merge Sort as Divide and Conquer in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the 'Divide and Conquer' approach in Merge Sort?

Divide the list into smaller parts, sort each part, then combine them back into a sorted list.

beginner

In Merge Sort, what happens after dividing the list into halves?

Each half is sorted recursively using Merge Sort until the base case of a single element is reached.

intermediate

Why is Merge Sort considered efficient for large lists?

Because it splits the list into smaller parts and merges them in a sorted way, leading to a time complexity of O(n log n).

beginner

What is the base case in the recursive Merge Sort algorithm?

When the list has one or zero elements, it is already sorted, so the recursion stops.

beginner

How does the merging step work in Merge Sort?

Two sorted lists are combined by repeatedly picking the smallest element from the front of each list until all elements are merged.

What is the first step in Merge Sort?

A Divide the list into two halves

B Merge two sorted lists

C Sort the entire list directly

D Find the largest element

Merge Sort starts by dividing the list into two halves before sorting.

What is the time complexity of Merge Sort?

A O(n^2)

B O(log n)

C O(n log n)

D O(n)

Merge Sort has a time complexity of O(n log n) due to dividing and merging steps.

When does the recursive splitting stop in Merge Sort?

A When the list has one or zero elements

B When the list is empty

C When the list is fully sorted

D When the list has two elements

The recursion stops when the list has one or zero elements, which are already sorted.

During merging, how do we pick elements from two sorted lists?

A Pick the largest element first

B Pick elements randomly

C Pick elements from the end

D Pick the smallest element from the front of each list

We pick the smallest element from the front of each list to maintain sorted order.

Which of these is NOT true about Merge Sort?

A It uses divide and conquer

B It sorts in place without extra space

C It has O(n log n) time complexity

D It merges sorted halves

Merge Sort requires extra space for merging and does not sort in place.

Explain how Merge Sort uses the divide and conquer strategy to sort a list.

Think about breaking down the problem and then combining solutions.

Describe the merging process in Merge Sort and why it is important.

Focus on how two sorted parts become one sorted whole.

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)