A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides several advantages: simple implementation, efficient for (quite) small data sets, adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position, and stable (i.e., does not change the relative order of elements with equal keys).