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 time

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

Read Similar Blogs: