Test by Bikram | Mock GATE | Test 3 | Question: 23

Question

Partitioning and Merging are the two main parts of $Quick Sort$.

 Which of the following is TRUE?

• A.     Partitioning is the key step while Merging is trivial.
• B.     Partitioning is trivial while Merging is the key step.
• C.     Both Partitioning and Merging are trivial.
• D.     Both Partitioning and Merging are key steps.

Comments

This is a vague question because "key" and "trivial" have no formal definition. But according to the context, A is the most correct option.

---

Partitioning is definitely important.

But the quicksort's second recursive call to itself can be replaced by an iterative procedure. This technique of replacing the second recursive call by an iterative sequence is called "tail recursion"

Merging is involved after partition, so maybe tail recursion can take care of it, and hence merging is trivial.

---

CLRS page 188.

Answer 1

In quick sort, partitioning is key as it needs selecting the pivot and then partitioning the array into two parts with one part > pivot and other <= pivot.
Merging is trivial where nothing is required.

Comments

What exactly key and trivial here Sir?

Answer 2

ANSWER IS (A.) Partitioning is the key step while Merging is trivial.

Answer 3

ANSWER IS (A.) Partitioning is the key step while Merging is trivial.