How does insertion sort work?

Question

How does insertion sort work?

Answer 1

More of a programming question than a Consumer Electronics question, but it basically works like this.

Say you have an array of unsorted elements called A. You then create an array of sorted elements called B by going through A one element at a time, and "inserting" them at the appropriate location in B.

Inserting is basically done by iterating through B until you find the point at which the element from A should be inserted, and then moving everything after that point down.

Wikipedia provides the following pseudo code:

insertionSort(array A) {

    for i = 1 to length[A]-1 {

        value = A[i]

        j = i-1

        while j >= 0 and A[j] > value {

            A[j + 1] = A[j]

            j = j-1

        }

        A[j+1] = value

   }

}

Answers doesn't permit indentation -- apologies. See references below for a link to a better example.