Insertion Sort [closed]

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

Insertion by ordering requires a number of permutations proportional to the square of the number of elements in the worst case ( O (n²)). 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 a number in the worst case case ( or(N log N) ).

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

In addition, it is worth mentioning the case of timsort. Timsort is a very complicated dynamic sorting algorithm that takes advantage of partial sorting in the data. It combines mergesort with insertion sort. When timsort detects that some Subpart to be sorted is nearly 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 are fine disorderly.