Insertion sort

Insertion Sort

Generate Random Numbers

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(n2) – Quadratic complexity for average cases.
  • Worst Case: O(n2) – 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(n2) worst-case complexity, it remains popular in certain applications due to its simplicity, low overhead, and adaptive nature.

Insertion Sort Code Implementation