Insertion Sort (Sorting by insertion)

Question

Could someone give me examples of everyday life in which the method of ordering by insertion is used?

Note: Without being ordering cards

Answer 1

In general, sorting is used in practice when the data set to be sorted is small or almost ordered.

Sorting insertion requires an amount of permutations proportional to the square of the number of elements in the worst case (O(n²)). The optimal algorithms (mergesort, heapsort, timsort, modern versions of shellsort, etc.) require in the worst case time proportional to the number of elements times the logarithm of such number in the worst case (O(n log n)).

However, when we are not talking about an sorting algorithm that deals with the worst case, when we know beforehand that the data to be ordered has few permutations, then sorting by insertion can be faster. Since the permutation process is much simpler than the sorting processes that are used by more complex algorithms (such as mergesort), for small data sets, insertion sorting can also be faster.

Also, mention the timsort case. Timsort is a very complicated dynamic sorting algorithm that takes advantage of partial data ordering. It combines mergesort with insertion ordering. When timsort detects that some subpart to be sorted is almost sorted or has a sufficiently small size, it will use insertion sorting on that part, while it will use mergesort on parts that are larger or very disordered.