Merge Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Merge Sort algorithm?

Merge Sort divides the list into two halves, sorts each half, and then merges the two sorted halves back together.

beginner

What is the time complexity of Merge Sort in the average and worst cases?

The time complexity of Merge Sort is O(n log n) for both average and worst cases.

intermediate

Why does Merge Sort require extra space?

Merge Sort needs extra space to hold temporary arrays during the merging process because it combines two sorted lists into one.

intermediate

Explain the merge step in Merge Sort.

The merge step takes two sorted halves and compares their elements one by one, placing the smaller element into a new array until all elements are merged in sorted order.

intermediate

Is Merge Sort a stable sorting algorithm? Why or why not?

Yes, Merge Sort is stable because it preserves the relative order of equal elements during the merge step.

What technique does Merge Sort use to sort the array?

A Divide and conquer

B Greedy

C Dynamic programming

D Brute force

Merge Sort splits the array into smaller parts, sorts them, and merges them back, which is divide and conquer.

What is the space complexity of Merge Sort?

A O(1)

B O(n log n)

C O(log n)

D O(n)

Merge Sort requires O(n) extra space for temporary arrays during merging.

During the merge step, what happens when elements from both halves are equal?

A The element from the right half is chosen first

B The element from the left half is chosen first

C Both elements are skipped

D The algorithm stops

To maintain stability, the element from the left half is chosen first when elements are equal.

Which of the following is true about Merge Sort's performance?

A It always divides the array into halves

B It has a worst-case time complexity of O(n^2)

C It is faster than Quick Sort in all cases

D It sorts in place without extra memory

Merge Sort always divides the array into two halves recursively.

What is the base case for the recursive Merge Sort function?

A When the array has more than two elements

B When the array is fully sorted

C When the array has one or zero elements

D When the array is empty

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

Describe step-by-step how Merge Sort sorts an array of numbers.

Think about splitting, sorting smaller parts, and merging.

Explain why Merge Sort is considered a stable sorting algorithm.

Focus on how equal elements are handled during merging.