A Rather Poor Merge Sort

Computer Science Level 2

Ryan is implementing a merge sort algorithm that he heard about in computers class. However, he wasn't paying attention, and ended up implementing the merge sort in a very unusual way.

The standard merge sort takes a list, and recursively splits it in half, until there is only one element left. It then uses the idea that two sorted lists can be easily merged in $O(n)$ time using "two pointer technique" (this step is usually called merge ).

Ryan doesn't know about two pointer technique, however, so he decided to replace merge with a bubble sort! The bubble sort runs in $O(n^2)$ time.

What is the runtime of this merge sort implementation?

O(n \log^2 n)

O(n^2)

O(n \log n)

O(n^2 \log n)

1 solution

Spencer Whitehead
Feb 3, 2016

We analyze this recurrence using the master method.

Note that the recurrence $T(n)$ can be written as follows: $T(n) = 2T\left(\frac{n}{2}\right) + O(n^2)$ This follows from the fact that we split the list in two, and recurse on each half. The $O(n^2)$ accounts for the worse runtime of the bubble sort than the merge function.

Now we note that $a=2, b=2, c=2$ , by the master method. Since $c > \log_b{a}$ , this falls under case 3. Therefore, $T(n) \in O(n^c), T(n) \in O(n^2)$ .

But won't the bubble sort run individually on all the partitions of the array. So that's log n * n^2. According to the Masters Theorem specified in CLRS, if you check the second vase taking a=b=2, we get O(n^2*log n). Could you please clarify it.

Himadri Sankar Chatterjee - 3 years, 2 months ago

An alternative solution would be the following (instead of applying the Masters Theorem):

T(n) = 2 T(n/2) + O(n^2) = 4 T(n/4) + O(.5 n^2 +n^2) = 8 T(n/8) + O(.25 n^2 + .5 n^2 + n^2)

Continuing in this fashion, we eventually obtain:

T(n) = O(n^2 + (1/2)n^2 + (1/4)n^2 +...+1).

This is a geometric series. It evaluates to O((n^2 - 1/2)*2) = O(n^2).

jason carlson - 2 years, 5 months ago

A Rather Poor Merge Sort

1 solution

0 pending reports