Sorting Algorithm Comparison
Sorting is one of the most important algorithms that pave way for other algorithms to work. Although in more complex algorithms we use language provided sorting functions, it is important to know how each of the sorting mechanisms work.
When we talk about sorting there are several sorting algorithms developers should be familiar with. Namely
Selection sort
Bubble sort
Insertion sort
Merge sort
Quick sort
Heap sort
Counting sort
Radix sort
Bucket sort
When comparing algorithms we can think of the following factors.
1. Number of swaps
This means how many times elements are being swapped
2. Use of recursion
This means if the algorithm is using recursive calls (calls to the same function within the same function). Recursion algorithms use stack heavily, so it affects the performance.
3. Number of comparisons
This means how many instances of comparison between two elements occur in the algorithm.
4. Amount of extra space required
This means if the algorithms use extra memory or not. Some algorithms use in place operations, meaning they move elements instead of creating new structures. Some algorithms create new structures to sort which requires more free memory to be available.
5. Stable vs Unstable
This means if the algorithm is capable of maintaining relative order of equal elements.
Let's compare the following sorting algorithms.
Algorithm | Recursion | Time Complexity | Space Complexity |
---|---|---|---|
Insertion | No | O(n) -> O(n*n) | O(1) |