To implement insertion sort in JAVA

By Sukriti Sinha

In this blog, we will discuss the idea of implementing insertion sort in JAVA with the help of algorithm and code.

In this blog, we will talk about the sorting algorithm: Insertion Sort

Input: An array or sequence of n numbers (a₁, a₂ … a_n).

Output: A permutation (reordering) of the given sequence such that they are arranged in ascending order.

The basic idea behind insertion sort is that we assume that the first element is already sorted. Then we compare the rest of the elements with the first element and accordingly place it in its correct position.

Algorithm:

INSERTON-SORT (A)

for j = 2 to A.length

key = A[j]

// Insert A[j] into the sorted sequence A[1..j-1]

i=j-1

while i>0 and A[i]>key

                A[i+1] =A[i]

                I = i-1

A[i+1] = key