Insertion sort is a simple sorting algorithm

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...

: a comparison sort

Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list...

 in which the sorted array

Sorted array

A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static lookup tables to hold multiple values which has the same...

 (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort

Heapsort

Heapsort is a comparison-based sorting algorithm to create a sorted array , and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O runtime...

, or merge sort

Merge sort

Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...

. However, insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive
  Adaptive sort
  A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of disorder – and sorts faster...
  
   (i.e., efficient) for data sets that are already substantially sorted: the time complexity
  Time complexity
  In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
  
   is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O
  Big O notation
  In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
  
  (n²)) algorithms such as selection sort
  Selection sort
  Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
  
   or bubble sort
  Bubble sort
  Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
  
  ; the best case (nearly sorted input) is O
  Big O notation
  In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
  
  (n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place
  In-place algorithm
  In computer science, an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes...
  
  ; i.e., only requires a constant amount O(1) of additional memory space
• Online
  Online algorithm
  In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
  
  ; i.e., can sort a list as it receives it

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.
Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.