Comparison of Sorts

Bubble Insertion Selection Shell Quick Merge Heap
Random
Nearly Sorted
Reversed
Few Unique

Key

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.
  • Dark gray values denote the current interval (shell, merge, quick).
  • A pair of red triangles marks the left and right pointers (quick).

For the above sorts, following order tells us which sort works faster than the other for a given type of input elements. The number of input elements is considered as greater than 30.

  1. Random
    Heap < Shell < Merge < Quick < Insertion < Bubble < Selection
  2. Nearly Sorted
    Insertion < Bubble < Shell < Heap < Merge < Quick < Selection
  3. Reversed
    Shell < Heap < Merge < Quick < Insertion < Bubble < Selection
  4. Few Unique
    Shell < Heap < Insertion < Merge < Quick < Bubble < Selection

Thus from the above animations it can be concluded that for input elements (20-50), Selection sort takes the longest time to sort. Insertion sort always takes lesser time compared to Bubble sort. Similarly, Heap sort takes lesser time than Merge sort which takes lesser time than Quick sort. For all cases, Heap and Shell sort take almost same time to arrange the input elements in ascending order.