A Sorting Algorithm is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
the sorting algorithms we talked about in the beginning where base on comparison now we want to see if we can sort an array without comparing the elements an if it is even possible to sort without comparison?. YES it is possible lets see an example: assume we have an array where the value in each cell is an integer let say the numbers are (1,4,2,5) now we create another array of size 5 and read every element from the initial array and write them in the cell where the index is equal to the value of the cell in the original array. as you can see with have sorted the array with zero comparison.
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input data set
| Table of Complexity Comparison: | ||||||
|---|---|---|---|---|---|---|
| Name | Best Case | Average Case | Worst Case | Memory | Stable | Method Used |
| Quick Sort | No | Partitioning | ||||
| Merge Sort | n | Yes | Merging | |||
| Heap Sort | 1 | No | Selection | |||
| Insertion Sort | n | 1 | Yes | Insertion | ||
| Tim Sort | n | n | Yes | Insertion & Merging | ||
| Selection Sort | 1 | No | Selection | |||
| Shell Sort | 1 | No | Insertion | |||
| Bubble Sort | n | 1 | Yes | Exchanging | ||
| Tree Sort | n | Yes | Insertion | |||
| Cycle Sort | 1 | No | Selection | |||
| Strand Sort | n | n | Yes | Selection | ||
| Cocktail Shaker Sort | n | 1 | Yes | Exchanging | ||
| Comb Sort | 1 | No | Exchanging | |||
| Gnome Sort | n | 1 | Yes | Exchanging | ||
| Odd–even Sort | n | 1 | Yes | Exchanging |