Insertion Sort (sort order) [closed]

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

Ordering insertion requires a quantity of permutations proportional to the square of the number of elements in the worst case ( O 2 ). The optimal algorithms (mergesort, heapsort, timsort, modern versions of shellsort, etc.) demand in the worst case time proportional to the number of elements times the logarithm of such number in the worst case ( n) ).

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

Also worth mentioning is the timsort case. Timsort is a very complicated dynamic ordering algorithm that takes advantage of partial ordering in the data. It combines mergesort with sorting by insertion. When timsort detects that a subpart to be ordered is almost ordered or has a sufficiently small size, it will use insert ordering in that part, while it will use mergesort in parts that are larger or are in a mess.