The Insertion Sort is a data sorting algorithm. The insertion sort is a fairly simple sorting algorithm. It has a complexity of
O(n+d) where d is the number of out-of-order elements, which makes it more efficient than its
Articles/Selection Sort counterpart.
Separate current element from list. Go down the list from that position until you either hit the beginning or find a value smaller. Insert the element in that spot. Repeat for all positions
--Sorting table tab --loop through every position in the table except the last one for i = 1, #tab - 1 do --store the value of the current element, and remove it from the table local value = table.remove(tab, i) --loop-control variable local t = i repeat t = t - 1 --if it is less than 1, it is the smallest if it is less than that position, t+1 until t < 1 or tab[t] <= value table.insert(tab, t + 1, value) end