Editing Insertion sort (section)

==Variants==
[[Donald Shell|D.L. Shell]] made substantial improvements to the algorithm; the modified version is called [[Shellsort|Shell sort]].  The sorting algorithm compares elements separated by a distance that decreases on each pass. Shell sort has distinctly improved running times in practical work, with two simple variants requiring O(''n''<sup>3/2</sup>) and O(''n''<sup>4/3</sup>) running time.<ref>{{Cite journal
 |last1=Frank
 |first1=R. M.
 |last2=Lazarus
 |first2=R. B.
 |year=1960
 |title=A High-Speed Sorting Procedure
 |journal=Communications of the ACM
 |volume=3
 |issue=1
 |pages=20–22
 |doi=10.1145/366947.366957|s2cid=34066017
 |doi-access=free
 }}</ref><ref name="Sedgewick2">
{{Cite journal
 |last=Sedgewick
 |first=Robert |author-link=Robert Sedgewick (computer scientist)
 |year=1986
 |title=A New Upper Bound for Shellsort
 |journal=Journal of Algorithms
 |volume=7
 |issue=2
 |pages=159–173
 |doi=10.1016/0196-6774(86)90001-5
 }}</ref>

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using ''binary insertion sort'' may yield better performance.<ref name=":0">{{Cite book |last=Samanta |first=Debasis |year=2008 |title=Classic Data Structures |publisher=PHI Learning |isbn=9788120337312 |pages=549}}</ref> Binary insertion sort employs a [[binary search algorithm|binary search]] to determine the correct location to insert new elements, and therefore performs {{nowrap|⌈log<sub>2</sub> ''n''⌉}} comparisons in the worst case. When each element in the array is searched for and inserted this is {{nowrap|O(''n'' log ''n'')}}.<ref name=":0"/> The algorithm as a whole still has a running time of O(''n''<sup>2</sup>) on average because of the series of swaps required for each insertion.<ref name=":0"/>

The number of swaps can be reduced by calculating the position of multiple elements before moving them. For example, if the target position of two elements is calculated before they are moved into the proper position, the number of swaps can be reduced by about 25% for random data. In the extreme case, this variant works similar to [[merge sort]].

A variant named ''binary merge sort'' uses a ''binary insertion sort'' to sort groups of 32 elements, followed by a final sort using [[merge sort]]. It combines the speed of insertion sort on small data sets with the speed of merge sort on large data sets.<ref>{{cite web
| title=Binary Merge Sort
| url=https://docs.google.com/file/d/0B8KIVX-AaaGiYzcta0pFUXJnNG8
|mode=cs2
}}</ref>

To avoid having to make a series of swaps for each insertion, the input could be stored in a [[linked list]], which allows elements to be spliced into or out of the list in constant time when the position in the list is known.<!-- Troubling statement when insert/delete is used. The typical insertion and deletion operations take O(n) if position is not known. The O(1) operations are cons/splice/rplacd. -->  However, searching a linked list requires sequentially following the links to the desired position: a linked list does not have random access, so it cannot use a faster method such as binary search.  Therefore, the running time required for searching is O(''n''), and the time for sorting is O(''n''<sup>2</sup>).<!-- Instead of search, a max operation is more appropriate. --> If a more sophisticated [[data structure]] (e.g., [[heap (data structure)|heap]] or [[binary tree]]) is used, the time required for searching and insertion can be reduced significantly; this is the essence of [[heap sort]] and [[binary tree sort]].

In 2006 Bender, [[Martin Farach-Colton]], and Mosteiro published a new variant of insertion sort called ''[[library sort]]'' or ''gapped insertion sort'' that leaves a small number of unused spaces (i.e., "gaps") spread throughout the array. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs with high probability in {{nowrap|O(''n'' log ''n'')}} time.<ref>{{cite journal
 |last1=Bender |first1=Michael A.
 |last2=Farach-Colton |first2=Martín |author-link2=Martin Farach-Colton
 |last3=Mosteiro |first3=Miguel A.
 |year=2006
 |title=Insertion sort is {{nowrap|''O''(''n'' log ''n'')}}
 |journal=Theory of Computing Systems
 |volume=39 |issue=3 |pages=391–397
 |arxiv=cs/0407003
 |doi=10.1007/s00224-005-1237-z
 |mr=2218409
 |s2cid=14701669
 }}</ref>

If a [[skip list]] is used, the insertion time is brought down to {{nowrap|O(log ''n'')}}, and swaps are not needed because the skip list is implemented on a linked list structure.  The final running time for insertion would be {{nowrap|O(''n'' log ''n'')}}.

===List insertion sort code in C===
If the items are stored in a linked list, then the list can be sorted with O(1) additional space.  The algorithm starts with an initially empty (and therefore trivially sorted) list. The input items are taken off the list one at a time, and then inserted in the proper place in the sorted list. When the input list is empty, the sorted list has the desired result.

<syntaxhighlight lang="c" line="1">
struct LIST * SortList1(struct LIST * pList) 
{
    // zero or one element in list
    if (pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while (pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if (head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while (p != NULL) {
                if (p->pNext == NULL || // last element of the sorted list
                    current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}
</syntaxhighlight>

The algorithm below uses a trailing pointer<ref>{{Citation |editor-last=Hill |editor-first=Curt |contribution=Trailing Pointer Technique |url=http://euler.vcsu.edu:7000/11421/ |title=Euler |publisher=Valley City State University |access-date=22 September 2012 |archive-date=26 April 2012 |archive-url=https://web.archive.org/web/20120426051041/http://euler.vcsu.edu:7000/11421/ |url-status=dead }}.</ref> for the insertion into the sorted list. A simpler recursive method rebuilds the list each time (rather than splicing) and can use O(''n'') stack space.

<syntaxhighlight lang="c">
struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL) {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}
</syntaxhighlight>