Project 3 - Best Sorting
There is no single best sorting algorithm. Quicksort is the fastest known comparison-based sorting algorithm when applied to large, unordered, sequences. It also has the advantage of being an in-place (or nearly in-place) sort. Unfortunately, quicksort has some weaknesses: its worst-case performance is \(\Theta(n^2) \), and it is not stable. Merge sort shares neither of these disadvantages: it is stable and it requires \(n log n \) steps in the worst case. Unfortunately, merge sort requires \(\Theta(n) \) additional space and it runs more slowly than quick sort on most inputs. The objective of this assignment is to write modified versions of merge and quicksort that exhibit better performance than the standard versions described in our textbook. You will implement three improvements (two for merge sort and one for quicksort) that should improve some aspect of the algorithm’s performance without requiring a great deal of additional code. You will also experimentally evaluate the impact of your improvements.
Categories:
11 minute read