Big O Comparison of Sorting Algorithms
In this session, we’re going to examine a few different sorting algorithms, and how to examine their “Big O” complexities.
In Groups of 2 or 3
Research the sorting algorithms above (or your instructors will assign one algorithm to your group).
Determine a small pseudocode implementation of the algorithm. Be prepared to share this within the class.
- How would you determine the “Big O” complexity of this algorithm?
- Is the complexity better, or worse, if the data is already sorted? Why?
- Does this algorithm need additional “space complexity” to do its work?
- Does this complexity matter if the data is smaller, or larger?
Analyzing the Complexity
We would typically speak of “worst-case scenario” with Big O analysis of any algorithm.
With sorting algorithms, though, we typically talk about “best case”, “worst case”, and “average case” scenarios. This allows us to compare the sorting algorithms more equally across all use cases. The “best/worst/average” considerations are speaking to the input data, not the algortihm itself.
- What would “best case” scenario be for your sorting algorithm?
- What is the “worst case” scenario for your sorting algorithm?
Bonus Points:
- Which sorting algorithm(s) does your program’s primary language (Ruby, JavaScript) use internally?
