How does insertion sort work step by step?

Insertion sort builds the sorted array one element at a time. Starting from the second element, it picks each element and inserts it into its correct position within the already-sorted part of the array, shifting larger elements to the right.

What is the time complexity of insertion sort?

Insertion sort has O(n) best-case time complexity on nearly sorted data, O(n²) average and worst-case complexity, and O(1) extra space.

Is insertion sort stable?

Yes. Insertion sort is stable because it inserts equal elements after previously placed equal elements, preserving their relative order, which is why it is used inside hybrid sorts like Timsort.

Insertion Sort

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Insertion Sort Overview

History

Insertion sort is one of the oldest sorting algorithms, dating back to the early days of computer science. It is inspired by the way people sort playing cards: by taking one card at a time and inserting it into its correct position within an already sorted portion of the deck.

First documented in the 1950s, it was commonly used in early computer systems due to its simplicity and ease of implementation. It was often used for sorting small data sets or nearly sorted data.

Current Uses

Small Data Sets: Insertion sort is often used for small datasets (typically less than 20 items).
Nearly Sorted Data: Particularly efficient for data that is already mostly sorted.
Embedded Systems: Used in some embedded systems and applications where memory space is limited.
Hybrid Algorithms: Often used in conjunction with other algorithms for small partitions.

Time and Space Complexity

Time Complexity

Best Case: O(n) - When the array is already sorted.
Average Case: O(n²) - Quadratic complexity for average cases.
Worst Case: O(n²) - When the array is sorted in reverse order.

Space Complexity

Space Complexity: O(1) - It is an in-place sorting algorithm requiring a constant amount of additional space.

Pseudo Code

function insertionSort(arr):
    for i from 1 to length(arr) - 1:
        key = arr[i]
        j = i - 1
        
        /* Move elements of arr[.0..i-1] that are greater than key 
           to one position ahead of their current position */
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
            
        arr[j + 1] = key
        
    return arr

Key Characteristics

Stability: Insertion sort is a stable sorting algorithm.
Adaptability: It performs better when the input is partially sorted.

Summary

Insertion sort is a straightforward and efficient algorithm for small or nearly sorted datasets. Despite its O(n²) worst-case complexity, it remains popular in certain applications due to its simplicity, low overhead, and adaptive nature.

How Insertion Sort Works

Think of sorting a hand of cards: you pick up each new card and slide it into its correct place among the cards you already hold. Insertion sort works the same way on the array:

Assume the first element is already a sorted sub-array of length one.
Pick the next element (the "key").
Shift all elements in the sorted part that are greater than the key one position to the right.
Insert the key into the vacated slot.
Repeat until every element has been inserted - the array is now sorted.

Because it only ever moves elements by adjacent shifts, insertion sort is stable and reaches near-linear O(n) behavior on data that is already mostly sorted.

When To Use Insertion Sort

Nearly sorted data: approaches O(n) and beats O(n log n) algorithms in practice.
Very small arrays: its low constant overhead makes it the fastest option.
Inside hybrid sorts: it is the finishing step of Timsort (JavaScript, Python) and Introsort (C++).
Online sorting: useful when elements arrive one at a time.

Insertion Sort Code Implementation