Sorting a always an improtant topic in computer science. A sorting algorithm is an algorithm that puts elements of a list into an ascending or descending order. Efficient sorting is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists. Sorting is also useful for producing human-readable outputs.
Time complexity vs. space complexity
The way that we used for efficiency are time complexity and space complexity. The “time complexity” of an algorithm measures how many “steps” the computer will have to perform to complete the algorithm. Time complexity itself is often split into “best-case”, “average-case”, and “worst-case”. categories when applicable. The “space complexity” of an algorithm measures how much computer memory will be used during the algorithm. In either case, the “Big O Notation” is often used to measure complexity.
As an example, in the “average case performance” for Insertion Sort is O(n2). What this means is that in the average case with an unsorted list of length n, the computer will have to perform “less than or equal to” C*n2 comparisons for some constant C. This puts an upper bound on how long the algorithm will take, and it gives a general sence of how much longer it will take if the size of the list increases.
Another example is sequential search vs. binary search. Suppose we have a list of length n and we want to search through this list for a particular value. A “sequential search” is where we simply look at every value in the list one by one to fing the value we’re looking for. In this case, the BigO of this algorithm would be O(n). Meanwhile, if we have sorted this list and try to find the same value in this list, we could use binary search which recursively check the “middle” value to subdivide the list into smaller lsits. In this case, the BigO of this binary search is O(log n). This is considered much faster than sequential search because log n << n.
Sorting Comparision
| Name | Best Case | Average Case | Worst Case | Memory | Stable |
| Bubble Sort | n | n2 | n2 | 1 | Yes |
| Insertion Sort | n | n2 | n2 | 1 | Yes |
| Selection Sort | n2 | n2 | n2 | 1 | No |
| Quick Sort | n log n | n log n | n log n | log n | No |
| Merge Sort | n log n | n log n | n log n | n | Yes |
| Heap Sort | n log n | n log n | n log n | 1 | No |