CSC 402

Linearithmic (N log N) sorts

In addition to the heap sort, these sorts work in linearithmic time.

Mergesort (S&W overview)

Basic algorithm:

1. Recursively sort first and second half of the array
2. Iterate through arrays copying next least element into a second array

Quicksort ( S&W overview)

Basic algorithm:

1. Select a "pivot" element and partition array elements to those less than the pivot and those greater than the pivot
2. Recursive sort the two partitions

Possible improvements:

• When size is small (e.g. less than 10), use a simple sort
• Place items equal to the pivot in the middle (3-way)
• Select pivot based on sample of 3

Discussion questions

• When does the quicksort take quadratic time?
• When should the quick sort be used?
• Should the merge sort ever be used?