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

Recall & Review

beginner

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

Divide the array into two halves, sort each half recursively, and then merge the two sorted halves into one sorted array.

beginner

In Merge Sort, what happens during the 'merge' step?

Two sorted subarrays are combined into a single sorted array by comparing elements one by one and placing the smaller element first.

intermediate

Why is Merge Sort considered efficient for large datasets?

Because it consistently divides the problem into smaller parts and merges them in O(n log n) time, which is faster than simple sorting methods like bubble sort for large data.

beginner

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

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

intermediate

How does Merge Sort handle the original array during sorting?

It does not sort in place; it uses extra space to merge sorted subarrays into a new array before copying back.

What is the time complexity of Merge Sort in the average case?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Merge Sort divides the array and merges in O(n log n) time consistently.

During Merge Sort, what is the size of the subarrays when the recursion stops?

A One or zero elements

B Two elements

C Half the original array

D The entire array

The base case is when the subarray has one or zero elements, which are already sorted.

Which step in Merge Sort combines two sorted arrays into one sorted array?

A Split step

B Divide step

C Merge step

D Sort step

The merge step combines two sorted arrays into one sorted array.

What kind of algorithm is Merge Sort?

A Backtracking

B Greedy

C Dynamic Programming

D Divide and Conquer

Merge Sort uses the divide and conquer strategy.

Does Merge Sort sort the array in place without extra space?

A Yes, it sorts in place

B No, it requires extra space for merging

C Only for arrays smaller than 10 elements

D Only if the array is already sorted

Merge Sort requires extra space to merge sorted subarrays.

Explain how Merge Sort uses the divide and conquer approach to sort an array.

Think about breaking the problem into smaller parts and then combining results.

Describe the merge step in Merge Sort and why it is important.

Focus on how two sorted parts become one sorted whole.