Sorting Revisted (More indepth)

Question 1

What are some mergesort properties?

Answer 1

Based on a recursive divide-and-conquer approach:

• If the list has 0 or 1 elements, done.
• Divide list into two lists of equal or nearly equal size and recursively sort each half.
• Finally, merge the two sorted halves into one sorted list.

Worst-case running time of Θ(n log n)

One of the best external (disk) sorting algorithms.

Works well for linked lists in addition to arrays/vectors

Question 2

Mergesort analysis

Answer 2

The number of comparisons used by mergesort on an input of size n satisfies a recurrence of the form:

T(n) = T([n/2]) + T([n/2]) + n

By induction, we see that T(n) is Θ(n lg n) for n a power of 2.

Base case: n = 0 or n = 1

Inductive hypothesis: T(n) = n lg n

Then (next inductive case):

T(2n) = 2T(n) + 2n (from recurrence)

= 2n lg n + 2n (substitute hypothesis)

= 2n(lg(2n) − 1) + 2n (note lg 2 = 1)

= 2n lg(2n) (simplify)

Question 3

Master Theorem for Divide-Conquer Recurrences

Answer 3

Question 4

What are some quicksort properties?

Answer 4

Quicksort is based on a recursive partitioning about a ‘pivot’:

• Pick any element as the pivot (many options here).
• Partition elements into three groups: less than (possibly equal to) pivot, equal to pivot, and more than (possibly equal to) pivot.
• Run quicksort on first and third partitions until one element.

In practice, a very fast internal sorting algorithm (almost twice as fast as mergesort)

On average good O(n lg n), but worst case input data leads to Ω( n² ) performance

Question 5

What are 3 different ways to choose a quicksort pivot?

Answer 5

1. Use passive pivot strategy (e.g. fixed position in range)
2. Use active pivot strategy (e.g. median-of-three)
3. Use random pivot strategy (more likely O(n lg n) performance)

Question 6

Quicksort recurrence relations and runtime

Answer 6

Best case is when partitioning gives partitions of the same size so cost is either

T(n) = 2T((n − 1)/2) + n for unique elements

or

T(n) = 2T(n/3) + n when duplicates allowed

Both recurrences are O(n lg n)

Worst case is when partitioning gives unbalanced partitions where cost is then

T(n) = T(n − 1) + n

which is O( n² )

Question 7

What is beadsort and what is its runtime complexity range?

Answer 7

Sorting algorithm which sorts positive integers by representing them in unary as a sequence of beads on a horizontal lines then uses gravity to sort them with the assistance of vertical rods

The algorithm’s run-time complexity ranges from O(1) to O(S), where S is the sum of the input integers