Sort inserts in C language

Inset sorting is the third and last of the simple sorting algorithms. First, it sorts the first two elements of the array. Then the algorithm inserts the third element in the appropriate order in relation to the first two elements. After that, he inserts the fourth item in the list of three items. This process is repeated until all elements are inserted. For example, when sorting a dcab array , each pass of the algorithm will look like this:

  Start dcab
 Pass 1 cdab
 Acdb pass 2
 Pass 3 abcd

An example of the implementation of sorting inserts is shown below:

  / * Sort by inserts.  * /
 void insert (char * items, int count)
 {

   register int a, b;
   char t;

   for (a = 1; a <count; ++ a) {
     t = items [a];
     for (b = a-1; (b> = 0) && (t <items [b]); b--)
       items [b + 1] = items [b];
     items [b + 1] = t;
   }
 }

Unlike bubble sorting and sorting by selection, the number of comparisons in sorting inserts depends on the initial ordering of the list. If the list is already sorted, the number of comparisons is n - 1; otherwise, its performance is of the order of n ² .

Generally speaking, in the worst cases, sorting by inserts is as bad as bubble sorting and sorting through selection, and on average it is only slightly better. However, sorting inserts have two advantages. First, her behavior is natural. In other words, it works the least when the array is already ordered, and most of all when the array is sorted in the reverse order. Therefore, sorting by inserts is an ideal algorithm for almost ordered lists. The second advantage is that this algorithm does not change the order of identical keys ^[1] . This means that if the list is sorted by two keys, then after sorting by inserts it will remain ordered by both.

Despite the fact that the number of comparisons with certain data sets can be quite low, each time you insert an element in its place, the array must be shifted. As a consequence, the number of movements can be significant.

^[1] That is, steady