Merge Sort Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Merge Sort algorithm?

Merge Sort works by dividing the list into smaller parts, sorting each part, and then merging them back together in order.

intermediate

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, where n is the number of elements to sort.

intermediate

Why is Merge Sort considered a stable sorting algorithm?

Merge Sort is stable because it keeps the original order of equal elements when merging the sorted parts.

beginner

Show the basic steps of Merge Sort on the array [4, 1, 3, 2].

Step 1: Divide into [4,1] and [3,2]<br>Step 2: Divide further to [4], [1], [3], [2]<br>Step 3: Merge [4] and [1] to get [1,4]<br>Step 4: Merge [3] and [2] to get [2,3]<br>Step 5: Merge [1,4] and [2,3] to get [1,2,3,4]

intermediate

What is the space complexity of Merge Sort and why?

Merge Sort has a space complexity of O(n) because it requires extra space to hold the temporary arrays during the merge process.

What technique does Merge Sort use to sort an array?

A Brute force

B Divide and conquer

C Dynamic programming

D Greedy approach

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

Which of the following is true about Merge Sort?

A It is a stable sorting algorithm

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

C It sorts in place without extra space

D It only works on sorted arrays

Merge Sort is stable because it preserves the order of equal elements during merging.

What is the first step in the Merge Sort algorithm?

A Divide the array into halves

B Merge two sorted arrays

C Compare all elements

D Swap elements

Merge Sort starts by dividing the array into two halves recursively.

How does Merge Sort combine the divided parts?

A By reversing the arrays

B By swapping elements randomly

C By sorting each part separately without merging

D By merging sorted subarrays

Merge Sort merges the sorted subarrays to form a fully sorted array.

What is the space complexity of Merge Sort?

A O(1)

B O(log n)

C O(n)

D O(n^2)

Merge Sort requires extra space proportional to the size of the array for merging, so space complexity is O(n).

Explain how Merge Sort sorts an array step-by-step.

Think about breaking the problem into smaller pieces and then combining them.

Describe the advantages and disadvantages of using Merge Sort.

Consider speed, memory use, and stability.