Are Selection or Insertion sort useful outside of

Question

Do these sorting algorithms have any use in real world application?

Or is it just a basic example of sorting algorithm with n^2 complexity?

Can anyone give some example of its usage?

Answer 1

HP / Microsoft std::sort() is introsort, quicksort with a depth parameter that switches to heapsort if the depth becomes too deep.

HP / Microsoft std::stable_sort() is a type of timsort. It uses insertion sort to create groups of 32 sorted elements, then uses bottom up merge sort to merge the groups.

On a side note, top down merge sort is not used in any common library that I'm aware of. Instead the common library versions for both internal (memory) and external (disk) merge sorts are all variations of bottom up merge sort (like timsort). Yet in a classroom environment or on web site articles, you see more examples of top down merge sort than bottom up merge sort.

Answer 2

Yes, insertion sort is widely used in industrial applications. That's mainly dues ot the fact that several popular C++ standard libraries such as libstdc++ and libc++ implement sort routine as a combination of insertion sort and depth-limited quicksort.

The idea is that insertion sort works very fast on nearly-sorted arrays, while for a straightforward implementation of quick sort sorted input leads to the worst-case behavior. Therefore the combined algorithm first applies a quicksort-like algorithm to partially sort the input, and then finished off with a call to insertion sort.

In libc++ insertion sort is also used for sorting by default if the input size is small enough (but larger than five elements, as sizes <= 5 are handled as special cases).

Answer 3

Insertion sort is one of the fastest sorting algorithm for sorting very small arrays.

In practice, many quicksort / mergesort implementations stop when the subarrays to sort is below certain threshold, and insertion sort is then used for these small arrays.

---

Selection sort is rarely used in practice.

Answer 4

Insertion sort is actually pretty fast for small input sizes, due to the small hidden constants in its complexity. Upto some size, insertion sort is faster than merge sort.

Thus, for many popular sorting algorithms, when the array size becomes very small, insertion sort is employed.

Bottomline: A O(N²) algorithm may be faster in practise than a O(N*logN) algorithm for sufficiently small sized inputs, owing to the hidden constants.