Insertion sort

Insertion sort is also commonly referred to as direct insertion sort. It is an efficient algorithm for sorting a small number of elements. Insertion sort is the simplest sort method. The basic idea of insertion sort is to insert a record into an already ordered table, thus creating a new ordered table with the number of records increased by 1. In its implementation process, a double-layer loop is used. The outer loop searches for all elements except the first element, and the inner loop searches for the position to be inserted in the ordered table in front of the current element and moves it.

The basic idea

Insertion sort works like many people sort a hand of cards. To start with, our left hand is empty and the cards on the table face down. Then, we take one card at a time from the table and insert it into the correct position in our left hand. To find the correct position of a card, we compare it from right to left with each card that is already in our hand. The cards held in the left hand are always sorted, which turns out to be the cards at the top of the pile on the table. Insertion sort means that in the element to be sorted, assuming that the previous number of n minus 1(where n>=2) is already sorted, we insert the NTH number into the previous sorted sequence, and then find the appropriate position, so that the sequence of the NTH number is also sorted. The process of inserting all elements in this way until the whole sequence is sorted is called insertion sort.

advantage

Insertion sort performs best when sorting nearly sorted arrays.

Demo animation

Sort a regular array

View slow demos, code, test cases

Sort an almost sorted array

View slow demos, code, test cases