Definition
Sorting Algorithms allows to sort data structures in a way that an algorithm promises for. Each sorting algorithm has internals whose performance criteria differs. The performance breakdowns and matrix are are demonstrated in the Big O Notation. I have given out some of the most commonly used sorting algorithms.
Sorting Algorithm Matrix
|
Algorithm |
Short Definition | Best Case | Average Case | Worse Case | Space Complexity |
| Bubble Sort | Adjacent elements are repeatedly compared and swapped. | O(n) | O(n2) | O(n2) | O(1) |
| Selection Sort | Largest element is selected, then the list is scanned until the smallest value is found accordingly swapped. | O(n2) | O(n2) | O(n2) | O(1) |
| Insertion Sort | It compares each element at a time starting from the second element in the data structure and comparing from the right to the left by inserting the lower element in its last position. | O(n) | O(n2) | O(n2) | O(1) |
| Shell Sort | Sub lists are with the elements in the given gap, swapped left and right depending on the number. When the gap is one, Insertion Sort is applied | O(n log n) | Depends on Gap Sequences | Depends on Gap Sequences | Depends on Gap Sequences |
| Heap Sort | Very efficient comparison based sorting algorithm that is similar to Selection Sort. It sorts the elements by building a heap using heapify and min/max until the array is sorted | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Quick Sort | It uses divide-and-conquer principle. It picks a pivot element, makes array subsets, lower on the left and greater on the right | O(n log n) | O(n log n) | O(n2) | O(log n) |
| Merge Sort | Yet another divide-and-conquer principle algorithm that divides the data structure to individuals, compares and merges them back to the resulting data structure. | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Radix Sort | The optimal algorithm for the numbers range from 1 to n2. It sorts and rearranges the array input elements for the each significant digit of the number. In each iteration the numbers are inserted into the buckets according to the current significant digit. | O(n * k) | O(n * k) | O(n * k) | O(n + k) |