Insertion Sort - Python

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list.

• The insertionSort function takes an array arr as input. It first calculates the length of the array (n). If the length is 0 or 1, the function returns immediately as an array with 0 or 1 element is considered already sorted.
• For arrays with more than one element, We start with second element of the array as first element in the array is assumed to be sorted.
• Compare second element with the first element and check if the second element is smaller then swap them.
• Move to the third element and compare it with the first two elements and put at its correct position
• Repeat until the entire array is sorted.

The provided example demonstrates the sorting process using the insertion sort algorithm. The initial array [12, 11, 13, 5, 6] is subjected to the insertionSort function. After sorting, the array should be [5, 6, 11, 12, 13]. The code prints the sorted array as the final output.

def insertionSort(arr): n = len(arr) # Get the length of the array if n <= 1: return # If the array has 0 or 1 element, it is already sorted, so return for i in range(1, n): # Iterate over the array starting from the second element key = arr[i] # Store the current element as the key to be inserted in the right position j = i-1 while j >= 0 and key < arr[j]: # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr) 

Output:

Sorted array is:
[5, 6, 11, 12, 13]

Time Complexity: O(N²) 
Auxiliary Space: O(1)

Please refer complete article on Insertion Sort for more details!