Sorting

Parameters

ParameterDescription
StabilityA sorting algorithm is stable if it preserves the relative order of equal elements after sorting.
In placeA sorting algorithm is in-place if it sorts using only O(1) auxiliary memory (not counting the array that needs to be sorted).
Best case complexityA sorting algorithm has a best case time complexity of O(T(n)) if its running time is at least T(n) for all possible inputs.
Average case complexityA sorting algorithm has an average case time complexity of O(T(n)) if its running time, averaged over all possible inputs, is T(n).
Worst case complexityA sorting algorithm has a worst case time complexity of O(T(n)) if its running time is at most T(n).

Stability in Sorting

Stability in sorting means whether a sort algorithm maintains the relative order of the equals keys of the original input in the result output.

So 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 unsorted array.

Consider a list of pairs:

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

Now we will sort the list using the first element of each pair.

A stable sorting of this list will output the below list:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

Because (9, 3) appears after (9, 7) in the original list as well.

An unstable sorting will output the below list:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

Unstable sort may generate the same output as the stable sort but not always.

Well-known stable sorts:

Well-known unstable sorts:



2016-07-21
2017-01-11
algorithm Pedia
Icon