Search

# Insertion Sort Implementation in Python

```# Function to do insertion sort
def insertionSort(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
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print arr[i]```

### Complexity Analysis of Insertion Sort

Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n)

Average Time Complexity [Big-theta]: O(n2)

Space Complexity: O(1)

Resources: Studytonight.com

Interviewbit.com

The Tech Platform

www.thetechplatform.com

### Recent Posts

See All

#### 5 Ways To Loop Through An Array In PHP

PHP, just like most other programming languages has multiple ways to loop through arrays. The most popular ways to do it usually is with a while, for and foreach operator, but, believe it or not, ther