# How insertion sort works?

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics

• Stable; i.e., does not change the relative order of elements with equal keys

# Sort an almost sorted array

## Claim

Insertion sort works the most efficient when the incoming or given array is almost sorted. The runtime in those cases are linear => O(n)

## Experiment

Let us actually prove the runtime is O(n) with sorting a set of randomly generated lists using ‘insertion sort’. Implementation of insertion-sort and results on running from a desktop (Mac — 4 core, 16 GB) is captured.

## Implementation

`from random import randintimport timedef insertion_sort(arr):    # Traverse through 1 to len(arr)    for i in range(1, len(arr)):        key = arr[i]        # Move elements of arr[0..i-1], that are        # greater than key, to one position ahead        # of their current position        j = i-1        while j >=0 and key < arr[j] :                arr[j+1] = arr[j]                j -= 1        arr[j+1] = keydef insertionSort(arr1):  t1 = time.time();  insertion_sort(arr1)  t2 = time.time();  print (str(len(arr1)) + ", " +  str(t2-t1))print ('Insertion Sort Beginning');for x in range(0,15):  # Creates arrays of various sizes with integers from 0-100 randomly sprawled about.   # They are named after the power of 10 the size is  toSort1 = [randint(0,100)] * randint(100000,10000000);  # Pre-sorts the array, insertion sort is faster for small inputs  sorted_list = sorted(toSort1);  ##################################  insertionSort(sorted_list);`

## Result:

Plotted the array size and the runtime and we can see the linear relationship.