Skip to main content
Practice

Understanding Insertion Sort in Depth

1. Setting Up the Loop​

Iterate over each element in the array, assuming the first element is already sorted.

Setting Up the Loop
for i in range(1, len(arr)):

2. Selecting the Current Element and Finding the Correct Position​

Select the current element, compare it with the previous elements, and find the appropriate position.

Selecting the Current Element and Finding the Correct Position
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
    arr[j + 1] = arr[j]
    j -= 1
arr[j + 1] = key

Time Complexity​

  1. Worst-case time complexity: O(n^2)

    • The worst-case occurs when the input array is sorted in reverse order. In this case, every new element needs to be compared with all previous elements in the already sorted portion of the array, requiring approximately (nxn) comparisons for n elements.

  2. Best-case time complexity: O(n)

    • This happens when the array is already sorted. Here, the correct position for each new element in the already sorted portion can be found immediately, requiring only one comparison per element. Thus, n comparisons are needed for an array of size n.

  3. Average time complexity: O(n^2)

    • In general cases where the array elements are arranged randomly, the average number of comparisons required is proportional to n^2.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.