# Insertion sort on a sorted array — O(n)

# 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**In-place**; i.e., only requires a constant amount O(1) of additional memory space**Online**; i.e., can sort a list as it receives it

# 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 randint

import 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] = key

def 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.**