Here is a concise classification of sorting algorithms:
Based on Number of Comparisons
Sorting algorithms can be categorized based on the number of comparisons required to sort the input. Using Big-O notation, most sorting algorithms require at least O(nlogn) comparisons in the best case and O(n^2) comparisons in the worst case[1][3].
Based on Recursion
Sorting algorithms are either recursive (e.g. quick sort), non-recursive (e.g. selection sort, insertion sort), or use a combination of both (e.g. merge sort)[1][2].
Based on Stability
Stable sorting algorithms maintain the relative order of elements with equal keys, while unstable sorting algorithms do not[1][3]. For example, insertion sort, merge sort, and bubble sort are stable, while heap sort and quick sort are unstable.
Based on Extra Space Requirement
Some sorting algorithms are "in-place" and require only O(1) or O(logn) extra space, such as insertion sort and quick sort. Others are "out-of-place" and require additional memory proportional to the input size, such as merge sort[1][3].
