# Insertion Sort in Python

def insertion_sort(arr):

n = len(arr)

for i in range(1, n):

key = arr[i]

j=i-1

# Move elements greater than key one position ahead

while j >= 0 and arr[j] > key:

arr[j + 1] = arr[j]

j=j-1

arr[j + 1] = key

# Driver code

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original List:", arr)

insertion_sort(arr)

print("Sorted List:", arr)

Insertion Sort in Python (Line-by-Line Explanation)

# Insertion Sort in Python

def insertion_sort(arr):

Explanation:

 def is used to define a function.

 arr is the list that needs to be sorted.

n = len(arr)

Explanation:

 len(arr) returns the total number of elements in the list.

 The value is stored in the variable n.

Example:

arr = [64, 34, 25, 12, 22]

n=5

for i in range(1, n):

Explanation:

 The for loop starts from index 1 because the first element (index 0) is already considered
sorted.

 The loop continues until the last element.

Example:
If n = 7, then i takes the values:

1, 2, 3, 4, 5, 6

key = arr[i]

Explanation:

 Stores the current element in a variable called key.

 This is the element that will be inserted into its correct position.

Example:

arr = [64, 34, 25, 12]

i=1

key = 34

j=i-1

Explanation:
  j points to the element just before the key.

 It is used to compare previous elements with the key.

Example:

i=1

j=0

while j >= 0 and arr[j] > key:

Explanation:
The while loop continues as long as:

1. j is a valid index (j >= 0).

2. The current element is greater than the key.

If both conditions are true, the larger element is shifted one position to the right.

arr[j + 1] = arr[j]

Explanation:

 Moves the larger element one position to the right.

Example:
Before:

[64, 34, 25]

After shifting:

[64, 64, 25]

j=j-1

Explanation:

 Moves j one position to the left.

 This allows the algorithm to continue comparing the key with earlier elements.

arr[j + 1] = key

Explanation:

 Inserts the key into its correct sorted position.

Example:
Before:
[64, 64, 25]

After insertion:

[34, 64, 25]

Driver Code

arr = [64, 34, 25, 12, 22, 11, 90]

Explanation:

 Creates a list of unsorted numbers.

print("Original List:", arr)

Explanation:

 Displays the list before sorting.

Output

Original List: [64, 34, 25, 12, 22, 11, 90]

insertion_sort(arr)

Explanation:

 Calls the insertion_sort() function to sort the list.

print("Sorted List:", arr)

Explanation:

 Displays the sorted list.

Output

Sorted List: [11, 12, 22, 25, 34, 64, 90]

Step-by-Step Working Example

Initial List:

[64, 34, 25, 12]

Pass 1 (i = 1)

key = 34

Compare 64 > 34 → Shift 64

[64, 34, 25, 12]

After:

[34, 64, 25, 12]

Pass 2 (i = 2)

key = 25

Compare 64 > 25 → Shift

Compare 34 > 25 → Shift

Before:

[34, 64, 25, 12]

After:

[25, 34, 64, 12]

Pass 3 (i = 3)

key = 12

Compare 64 > 12 → Shift

Compare 34 > 12 → Shift

Compare 25 > 12 → Shift

Before:

[25, 34, 64, 12]

After:

[12, 25, 34, 64]

Final Sorted List

Summary

 The algorithm starts with the second element.

 It treats the left part of the list as already sorted.

 Each new element (key) is compared with previous elements.

 Larger elements are shifted to the right.

 The key is inserted into its correct position.

 The process repeats until the entire list is sorted.

Definition

Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted list one element
at a time. It picks one element from the unsorted portion and inserts it into its correct position in the
sorted portion of the list, similar to the way people arrange playing cards in their hands.

Steps of Insertion Sort

1. Assume the first element is already sorted.

2. Select the next element (called the key).

3. Compare the key with the elements before it.

4. Shift all elements that are greater than the key one position to the right.

5. Insert the key into its correct position.

6. Repeat the process for all remaining elements until the list is completely sorted.

Example

Consider the array:

Before Sorting:

[64, 34, 25, 12]

Pass 1

 Key = 34

 Compare 34 with 64.

 Shift 64 to the right.

 Insert 34.

[34, 64, 25, 12]

Pass 2

 Key = 25

 Compare with 64 → Shift

 Compare with 34 → Shift

 Insert 25.

[25, 34, 64, 12]

Pass 3

 Key = 12
  Compare with 64 → Shift

 Compare with 34 → Shift

 Compare with 25 → Shift

 Insert 12.

[12, 25, 34, 64]

Sorted Array:

[12, 25, 34, 64]

Time Complexity

Case Time Complexity

Best Case (Already Sorted) O(n)

Average Case O(n²)

Worst Case (Reverse Sorted) O(n²)

Space Complexity

 O(1) (Constant extra space)

 It is an in-place sorting algorithm, meaning it does not require additional memory.

Advantages

1. Simple and easy to understand and implement.

2. Efficient for small datasets.

3. Performs well when the data is already or nearly sorted.

4. Requires only O(1) extra memory (in-place sorting).

5. It is a stable sorting algorithm, meaning equal elements maintain their original order.

6. Suitable for online sorting, where elements are received one at a time.

Disadvantages

1. Inefficient for large datasets because its average and worst-case time complexity is O(n²).

2. Requires many comparisons and shifts when the array is reverse sorted.

3. Slower than efficient algorithms such as Merge Sort, Quick Sort, and Heap Sort for large
inputs.
 4. Not suitable for sorting large amounts of data.

Applications

 Sorting small arrays or lists.

 Sorting nearly sorted data.

 Used as a subroutine in advanced sorting algorithms (such as Timsort).

 Suitable for educational purposes due to its simple logic.

Summary

Feature Insertion Sort

Sorting Method Comparison-based

Technique Incremental insertion

Best Time Complexity O(n)

Average Time Complexity O(n²)

Worst Time Complexity O(n²)

Space Complexity O(1)

Stable Yes

In-place Yes

Suitable For Small or nearly sorted datasets