Classification of Sorting Algorithms

Stable Vs Unstable Sorting

Stable sort sorts the identical elements in their same order as they appear in the input.
Examples: Bubble sort, Insertion sort, Merge Sort, Counting sort

In unstable sort, order of identical elements is not guranteed to stay in the same order as they appeared in the input. Examples: Quick Sort, Heap Sort, Selection sort

  • Stability is not an issue when equal elements are indistinguishable such as with integers.
  • Any given sorting algorithm which is not stable can be modified to stable.
  • Generally, unstable sorting is faster than stable sorting.
  • We need a stable sort to sort the cards by their numbers and suit.

Internal Vs External Sort

Internal sorting is that which takes place entirely within the main memory of computer. It comes into role when the dataset is small.

External sorting is that which can handle massive amount of data at a time. Data reside in hard disk in case of external sorting.

Comparison based Sorting  and Counting based Sorting

In Comparison based sorting, a comparator is required to compare numbers or items. This comparator defines the ordering to arrange the elements.
Examples: Merge Sort, Quick Sort, Heap Sort

Counting based sorting is the algorithm that perform the sorting without comparing the elements rather by making certain assumption about the data they are going to sort.
Examples: Counting sort, Radix sort

In-Place and Not-In-Place Sorting

In-Place Sorting means to sort the array by modifying the element order directly within the array.

  • No auxiliary data structure is used.
  • There can be only constant amount of extra space usually less than log(n). So this algorithm is space efficient.

Examples: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort

Not-In-Place Sorting is that which uses auxiliary data structure to sort the array.
Examples: Merge Sort ( It requires additional O(n) space to perform the merge operation), Quick Sort