Insertion Sort: flowchart, algorithm and program

This program reads n numbers into an array and sorts them in ascending order using insertion sort, then prints the result. It works like sorting playing cards in your hand: take the next card and slide it into the correct place among the cards already sorted.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Set i = 0.
  4. Step 4: If i < n, go to step 5; otherwise go to step 7.
  5. Step 5: Read arr[i].
  6. Step 6: Increase i by 1. Go to step 4.
  7. Step 7: Set i = 1.
  8. Step 8: If i < n, go to step 9; otherwise go to step 14.
  9. Step 9: Set key = arr[i]; j = i - 1.
  10. Step 10: If j >= 0 and arr[j] > key, go to step 11; otherwise go to step 12.
  11. Step 11: arr[j+1] = arr[j]; j--. Go to step 10.
  12. Step 12: arr[j+1] = key.
  13. Step 13: Increase i by 1. Go to step 8.
  14. Step 14: Set i = 0.
  15. Step 15: If i < n, go to step 16; otherwise go to step 18.
  16. Step 16: Print arr[i].
  17. Step 17: Increase i by 1. Go to step 15.
  18. Step 18: Print newline.
  19. Step 19: Stop.

Pseudocode

BEGIN
    READ n
    i ← 0
    WHILE i < n DO
        READ arr[i]
        i++
    END WHILE
    i ← 1
    WHILE i < n DO
        key ← arr[i]; j ← i - 1
        WHILE j >= 0 and arr[j] > key DO
            arr[j+1] ← arr[j]; j--
        END WHILE
        arr[j+1] ← key
        i++
    END WHILE
    i ← 0
    WHILE i < n DO
        PRINT arr[i]
        i++
    END WHILE
    PRINT newline
END

Program in C, Python and Java

Insertion Sort program in C

#include <stdio.h>

int main() {
    int n, i, j, key;
    int arr[100];

    printf("Enter n: ");
    scanf("%d", &n);

    printf("Enter %d numbers: ", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }

    printf("Sorted array: ");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Insertion Sort program in Python

n = int(input("Enter n: "))
arr = list(map(int, input("Enter " + str(n) + " numbers: ").split()))

for i in range(1, n):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

print("Sorted array:", end=" ")
for i in range(n):
    print(arr[i], end=" ")
print()

Insertion Sort program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter n: ");
        int n = sc.nextInt();
        int[] arr = new int[n];

        System.out.print("Enter " + n + " numbers: ");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }

        System.out.print("Sorted array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Sample input: n = 5, numbers = 64 25 12 22 11
Output: Sorted array: 11 12 22 25 64

How it works

  • The outer loop starts at i = 1, because arr[0] on its own is already a sorted part of size one.
  • At each step, key = arr[i] is the number we want to place, and j = i - 1 points to the last element of the sorted part.
  • The while loop runs while j >= 0 and arr[j] > key. Each time, arr[j] is copied one place to the right (arr[j + 1] = arr[j]) and j-- moves left, making a gap for key.
  • When the loop stops, either j has gone below 0 or arr[j] is not bigger than key, so the gap is at j + 1 and we write arr[j + 1] = key.
  • After i reaches n - 1, the whole array is sorted, and a final loop prints it. For 64 25 12 22 11 the output is 11 12 22 25 64.

Dry run (trace table)

StepLineBoxniarrkeyjOutput
13Start
28Read n5
311i = 050
411i < n?50
512Read arr[i]50[64]
611i++51[64]
711i < n?51
812Read arr[i]51[64,25]
911i++52[64,25]
1011i < n?52
1112Read arr[i]52[64,25,12]
1211i++53[64,25,12]
1311i < n?53
1412Read arr[i]53[64,25,12,22]
1511i++54[64,25,12,22]
1611i < n?54
1712Read arr[i]54[64,25,12,22,11]
1811i++55[64,25,12,22,11]
1911i < n?55
2015i = 151[64,25,12,22,11]

Time and space complexity

Time: O(n²) · Space: O(1). For each of the n elements the inner while loop may shift up to n elements, and sorting is done in place with only a few extra variables.

Common mistakes

  • Writing the while condition as arr[j] > key && j >= 0. The j >= 0 check must come first, otherwise arr[-1] is read when j becomes -1.
  • Forgetting to save key = arr[i] before shifting. The shift overwrites arr[i], and the original value is lost.
  • Placing key at arr[j] instead of arr[j + 1] after the loop. The loop ends one position past the correct slot, so the gap is at j + 1.
  • Starting the outer loop at i = 0 instead of 1. It still works, but it does a useless pass.

Viva questions

Q1. Why does the outer loop on line 15 start from i = 1 and not i = 0?

A single element, arr[0], is already a sorted sub-array by itself. So we start with the second element and insert it into the sorted part on its left.

Q2. What is the purpose of the variable key on line 16?

key stores the value arr[i] that we want to insert. The while loop shifts larger elements to the right, which overwrites arr[i], so without key that value would be lost.

Q3. Explain the condition j >= 0 && arr[j] > key in the while loop. Why are both parts needed?

arr[j] > key means the element is larger than key and must shift right. j >= 0 stops the loop at the start of the array, so we never read arr[-1]. If j >= 0 were missing, the program would read outside the array. The order also matters: && short-circuits, so arr[j] is not evaluated once j < 0.

Q4. Why is the key placed at arr[j + 1] on line 22 and not at arr[j]?

When the while loop stops, j points to the element that is smaller than or equal to key, or to -1. The correct position for key is just after it, which is j + 1.

Q5. What happens if the user enters n = 1, n = 0, or a negative n?

For n = 1 the outer loop never runs, so the single element is printed as it is. For n = 0 or negative, nothing is read or sorted, and the program prints only 'Sorted array:'. There is no check for n > 100, so a larger n overflows arr[100], which is undefined behaviour.

Q6. Is this insertion sort stable? Which part of the code decides that?

Yes, it is stable. The comparison uses strict > and not >=, so equal elements are never shifted past each other and keep their original relative order.

Q7. What are the best-case, worst-case and average-case time complexities of this program? What is the space complexity?

Best case is O(n), when the array is already sorted, because the while loop never runs. Worst case (reverse sorted) and average case are O(n^2), because of the shifting. Space is O(1) extra, since the sort is done in place using only key, i and j.

Q8. What would you change to sort in descending order?

Change the condition arr[j] > key to arr[j] < key on line 18. Then smaller elements are shifted right and larger ones move to the front. Nothing else needs to change.

Frequently asked questions

What is the time complexity of insertion sort?

The worst case and average case are O(n^2), when the array is in reverse or random order. The best case is O(n) for an already sorted array, since the while loop never shifts anything.

Is insertion sort stable?

Yes. It only shifts elements that are strictly greater than key (arr[j] > key), so equal elements keep their original relative order.

When should I use insertion sort over other sorts?

It is a good choice for small or nearly sorted arrays because it is simple, sorts in place with O(1) extra space, and runs close to O(n) on nearly sorted data. For large random data, merge sort or quick sort are faster.

More programs

← All programs

Try AI Flowchart free →