Insertion sort on a sorted array – O(n)

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

In this post we will see the results of runtime of insertion sort on a set of random lists. Implementation of insertion-sort and the experiment setup.

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: