Sorting algorithms can be categorised based on the following parameters:
- Based on Number of Swaps or Inversion. This is the number of times the algorithm swaps elements to sort the input.
Selection Sort
requires the minimum number of swaps. - Based on Number of Comparisons. This is the number of times the algorithm compares elements to sort the input. Using Big-O notation, the sorting algorithm examples listed above require at least
O(n log n)
comparisons in the best case andO(n2)
comparisons in the worst case for most of the outputs. - Based on Recursion or Non-Recursion. Some sorting algorithms, such as
Quick Sort
, use recursive techniques to sort the input. Other sorting algorithms, such asSelection Sort
orInsertion Sort
, use non-recursive techniques. Finally, some sorting algorithm, such asMerge Sort
, make use of both recursive as well as non-recursive techniques to sort the input. - Based on Stability. Sorting algorithms are said to be
stable
if the algorithm maintains the relative order of elements with equal keys. In other words, two equivalent elements remain in the same order in the sorted output as they were in the input.Insertion sort
,Merge Sort
, andBubble Sort
are stableHeap Sort
andQuick Sort
are not stable
- Based on Extra Space Requirement. Sorting algorithms are said to be in place if they require a constant
O(1)
extra space for sorting.Insertion sort
andQuick-sort
arein place
sort as we move the elements about the pivot and do not actually use a separate array which is NOT the case in merge sort where the size of the input must be allocated beforehand to store the output during the sort.Merge Sort
is an example ofout place
sort as it require extra memory space for it’s operations.