Sorting is an important part of algorithms. This has been feild in computer science which got lot of attention through reasearch papers and books. In this blog we will learn about different sorting algorithms and why they work like that.
During the studies i always have the question of how do in-built function know to sort any input type. So in in-built function there exists a callback function which is called by the function which needs to be sorted. For example it can be compareTo() (using comparable Interface) in java and compare() in C which identify the input type. At the end it can end up in function which ask less() and exch()/swap().
| Name | Time Complexity | Space Complexity | Stability | Inplace | Application |
|---|---|---|---|---|---|
| Bubble Sort | O(n^2) | O(1) | Yes | Yes | |
| Selection Sort | O(n^2) | O(1) | No | Yes | - |
| Insertion Sort | O(n^2) | O(1) | Yes | No | On ascendingrly input insertion sort is preferred over merge sort beacuse of less compares and swaps |
| Merge Sort | O(n log n) | O(n) | Yes | No | - |
| Quick Sort | O(n log n) | O(log n) | No | Yes | - |
| Heap Sort | O(n log n) | O(1) | No | No | - |
| Counting Sort | O(n + k) | O(n + k) | Yes | Yes | - |
| Bucket Sort | O(n + k) | O(n + k) | No | Yes | - |
| Radix Sort | O(nk) | O(n + k) | Yes | No | - |