Insertion Sort

Overview

Insertion Sort operates by maintaining a sorted portion of an array and iteratively placing each unsorted element into its correct position within that sorted portion. The algorithm starts with the first element as the initial sorted portion, then examines each subsequent element and inserts it backward into the sorted portion until finding its correct position.

The algorithm derives its name from the insertion operation: taking an element from the unsorted portion and inserting it into the appropriate position in the sorted portion. This process mirrors how people often sort playing cards in their hands—picking up one card at a time and placing it in the correct position among the cards already held.

Insertion Sort belongs to the class of comparison-based sorting algorithms, meaning it determines element order by comparing pairs of elements. Unlike divide-and-conquer algorithms such as Merge Sort or Quick Sort, Insertion Sort uses an incremental approach that builds the solution piece by piece.

The algorithm demonstrates particular efficiency with small datasets or nearly sorted data. Modern quick sort implementations often switch to Insertion Sort when sorting small subarrays, as the overhead of more complex algorithms outweighs their theoretical advantages for small input sizes.

# Basic insertion sort implementation
def insertion_sort(arr)
  (1...arr.length).each do |i|
    key = arr[i]
    j = i - 1
    
    while j >= 0 && arr[j] > key
      arr[j + 1] = arr[j]
      j -= 1
    end
    
    arr[j + 1] = key
  end
  arr
end

array = [5, 2, 8, 1, 9]
insertion_sort(array)
# => [1, 2, 5, 8, 9]

Key Principles

Insertion Sort operates on the principle of maintaining an invariant: at any point during execution, elements from index 0 to i-1 form a sorted sequence. The algorithm processes element i by finding where it belongs within this sorted sequence and inserting it there while maintaining the sorted property.

Core Mechanism

The algorithm divides the array into two conceptual regions: a sorted region at the beginning and an unsorted region at the end. Initially, the sorted region contains only the first element, as a single element is trivially sorted. The algorithm then expands the sorted region by one element per iteration.

For each element in the unsorted region, the algorithm:

1. Removes the element from its current position
2. Compares it with elements in the sorted region from right to left
3. Shifts elements in the sorted region one position to the right if they are greater than the current element
4. Inserts the current element when finding a smaller element or reaching the beginning

Shifting Operation

The shifting operation distinguishes Insertion Sort from selection-based algorithms. When inserting an element, the algorithm does not swap elements pairwise. Instead, it shifts multiple elements one position to create space for insertion. This approach requires fewer writes than repeated swapping.

# Demonstrating the shifting mechanism
def insertion_sort_verbose(arr)
  (1...arr.length).each do |i|
    key = arr[i]
    puts "Inserting #{key} from position #{i}"
    j = i - 1
    
    while j >= 0 && arr[j] > key
      puts "  Shifting #{arr[j]} from position #{j} to #{j + 1}"
      arr[j + 1] = arr[j]
      j -= 1
    end
    
    arr[j + 1] = key
    puts "  Placed #{key} at position #{j + 1}"
    puts "  Array state: #{arr.inspect}"
  end
  arr
end

In-Place Property

Insertion Sort operates in-place, requiring only O(1) additional memory beyond the input array. The algorithm rearranges elements within the original array structure without allocating auxiliary data structures. This characteristic makes Insertion Sort suitable for memory-constrained environments.

Stability

The algorithm maintains stability when properly implemented. Stability means that elements with equal values retain their relative order from the input. Insertion Sort achieves stability because it only shifts elements that are strictly greater than the key being inserted, never shifting equal elements past each other.

Adaptive Behavior

Insertion Sort exhibits adaptive behavior: its performance improves as input data approaches sorted order. For already sorted data, the inner while loop never executes, reducing time complexity from O(n²) to O(n). This adaptiveness makes the algorithm efficient for maintaining sorted data structures that receive small numbers of insertions.

Ruby Implementation

Ruby's object-oriented nature and expressive syntax enable concise Insertion Sort implementations. The language provides multiple approaches for implementing the algorithm, from procedural to functional styles.

Standard Implementation

def insertion_sort(array)
  (1...array.length).each do |i|
    current = array[i]
    position = i - 1
    
    while position >= 0 && array[position] > current
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[position + 1] = current
  end
  array
end

Non-Mutating Implementation

Ruby developers often prefer non-mutating operations that return new objects rather than modifying existing ones:

def insertion_sort_immutable(array)
  result = array.dup
  (1...result.length).each do |i|
    current = result[i]
    position = i - 1
    
    while position >= 0 && result[position] > current
      result[position + 1] = result[position]
      position -= 1
    end
    
    result[position + 1] = current
  end
  result
end

original = [5, 2, 8, 1]
sorted = insertion_sort_immutable(original)
# original remains [5, 2, 8, 1]
# sorted is [1, 2, 5, 8]

Custom Comparison Implementation

Ruby's block syntax allows passing custom comparison logic:

def insertion_sort_with_block(array, &comparator)
  comparator ||= proc { |a, b| a <=> b }
  
  (1...array.length).each do |i|
    current = array[i]
    position = i - 1
    
    while position >= 0 && comparator.call(array[position], current) > 0
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[position + 1] = current
  end
  array
end

# Sort in descending order
numbers = [3, 1, 4, 1, 5]
insertion_sort_with_block(numbers) { |a, b| b <=> a }
# => [5, 4, 3, 1, 1]

# Sort strings by length
words = ["ruby", "go", "javascript", "c"]
insertion_sort_with_block(words) { |a, b| a.length <=> b.length }
# => ["c", "go", "ruby", "javascript"]

Sorting Complex Objects

Ruby objects can be sorted based on any attribute or computation:

class Task
  attr_reader :priority, :name
  
  def initialize(name, priority)
    @name = name
    @priority = priority
  end
  
  def to_s
    "#{@name} (priority: #{@priority})"
  end
end

def sort_tasks(tasks)
  (1...tasks.length).each do |i|
    current = tasks[i]
    position = i - 1
    
    while position >= 0 && tasks[position].priority > current.priority
      tasks[position + 1] = tasks[position]
      position -= 1
    end
    
    tasks[position + 1] = current
  end
  tasks
end

tasks = [
  Task.new("Email", 3),
  Task.new("Meeting", 1),
  Task.new("Code Review", 2)
]

sort_tasks(tasks)
# => [Meeting (priority: 1), Code Review (priority: 2), Email (priority: 3)]

Integration with Enumerable

Extending Array with insertion sort functionality:

class Array
  def insertion_sort!
    (1...length).each do |i|
      current = self[i]
      position = i - 1
      
      while position >= 0 && self[position] > current
        self[position + 1] = self[position]
        position -= 1
      end
      
      self[position + 1] = current
    end
    self
  end
  
  def insertion_sort
    dup.insertion_sort!
  end
end

[5, 2, 8, 1].insertion_sort
# => [1, 2, 5, 8]

Practical Examples

Sorting User Input

Processing user-provided data that arrives incrementally:

class SortedList
  def initialize
    @items = []
  end
  
  def insert(value)
    @items << value
    position = @items.length - 1
    
    while position > 0 && @items[position - 1] > @items[position]
      @items[position], @items[position - 1] = @items[position - 1], @items[position]
      position -= 1
    end
    
    @items
  end
  
  def to_a
    @items.dup
  end
end

list = SortedList.new
list.insert(5)  # => [5]
list.insert(2)  # => [2, 5]
list.insert(8)  # => [2, 5, 8]
list.insert(1)  # => [1, 2, 5, 8]

Sorting File Data

Reading and sorting data from files where the dataset fits in memory:

def sort_log_entries(filename)
  entries = File.readlines(filename).map(&:strip)
  
  (1...entries.length).each do |i|
    current = entries[i]
    timestamp = extract_timestamp(current)
    position = i - 1
    
    while position >= 0 && extract_timestamp(entries[position]) > timestamp
      entries[position + 1] = entries[position]
      position -= 1
    end
    
    entries[position + 1] = current
  end
  
  entries
end

def extract_timestamp(log_entry)
  # Extract timestamp from log format: "[2025-01-15 10:30:45] message"
  log_entry[/\[(.*?)\]/, 1]
end

Optimizing Nearly Sorted Data

Insertion Sort excels with nearly sorted data, common in real-time systems:

class SensorDataProcessor
  def initialize
    @readings = []
  end
  
  def add_reading(timestamp, value)
    reading = { timestamp: timestamp, value: value }
    @readings << reading
    
    # Most readings arrive in order; sort only recent additions
    if @readings.length > 1
      position = @readings.length - 1
      current = @readings[position]
      
      while position > 0 && @readings[position - 1][:timestamp] > current[:timestamp]
        @readings[position] = @readings[position - 1]
        position -= 1
      end
      
      @readings[position] = current
    end
  end
  
  def recent_readings(count)
    @readings.last(count)
  end
end

processor = SensorDataProcessor.new
processor.add_reading(Time.now, 23.5)
sleep(1)
processor.add_reading(Time.now, 24.1)
sleep(1)
processor.add_reading(Time.now, 23.8)

Hybrid Sorting Approach

Combining Insertion Sort with faster algorithms for different data sizes:

def hybrid_sort(array, threshold = 10)
  return insertion_sort(array.dup) if array.length <= threshold
  
  # Use quicksort for larger arrays
  quick_sort(array, 0, array.length - 1, threshold)
end

def quick_sort(array, low, high, threshold)
  return if low >= high
  
  # Switch to insertion sort for small subarrays
  if high - low + 1 <= threshold
    insertion_sort_range(array, low, high)
    return
  end
  
  pivot_index = partition(array, low, high)
  quick_sort(array, low, pivot_index - 1, threshold)
  quick_sort(array, pivot_index + 1, high, threshold)
  array
end

def insertion_sort_range(array, start, finish)
  ((start + 1)..finish).each do |i|
    current = array[i]
    position = i - 1
    
    while position >= start && array[position] > current
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[position + 1] = current
  end
end

Performance Considerations

Time Complexity Analysis

Insertion Sort exhibits quadratic time complexity in the average and worst cases. The algorithm performs O(n²) comparisons and shifts when processing randomly ordered or reverse-ordered data. Each element potentially requires comparison with all elements in the sorted portion, leading to approximately n²/2 comparisons across all iterations.

For already sorted data, time complexity reduces to O(n) because the inner loop never executes. The algorithm performs exactly n-1 comparisons, one for each element after the first. This best-case scenario makes Insertion Sort competitive with more sophisticated algorithms for nearly sorted data.

The space complexity remains O(1) as the algorithm operates in-place, requiring only a constant amount of additional memory for loop variables and the temporary key storage.

Comparison Count Analysis

def insertion_sort_with_metrics(array)
  comparisons = 0
  shifts = 0
  
  (1...array.length).each do |i|
    current = array[i]
    position = i - 1
    
    while position >= 0
      comparisons += 1
      break unless array[position] > current
      
      array[position + 1] = array[position]
      shifts += 1
      position -= 1
    end
    
    array[position + 1] = current
  end
  
  { array: array, comparisons: comparisons, shifts: shifts }
end

# Random data
result = insertion_sort_with_metrics([5, 2, 8, 1, 9, 3])
# => { array: [1, 2, 3, 5, 8, 9], comparisons: 12, shifts: 9 }

# Already sorted data
result = insertion_sort_with_metrics([1, 2, 3, 4, 5])
# => { array: [1, 2, 3, 4, 5], comparisons: 4, shifts: 0 }

# Reverse sorted data
result = insertion_sort_with_metrics([5, 4, 3, 2, 1])
# => { array: [1, 2, 3, 4, 5], comparisons: 10, shifts: 10 }

Performance Characteristics by Input Type

Best case: O(n) when data is already sorted or nearly sorted. Each element requires only one comparison to determine it is already in correct position.

Average case: O(n²) when data is randomly ordered. On average, each element must be compared with half the elements in the sorted portion.

Worst case: O(n²) when data is reverse sorted. Each element must be compared with all elements in the sorted portion and shifted to the beginning of the array.

Cache Performance

Insertion Sort demonstrates good cache locality because it accesses array elements sequentially and operates on a small working set. The algorithm reads elements from left to right and writes in nearby positions, maximizing cache hits. This characteristic provides practical performance advantages over algorithms with scattered memory access patterns, particularly for small to medium datasets.

Practical Threshold Determination

require 'benchmark'

def find_optimal_threshold
  sizes = [10, 20, 50, 100, 200, 500]
  results = {}
  
  sizes.each do |size|
    random_data = Array.new(size) { rand(1000) }
    
    time_insertion = Benchmark.measure do
      1000.times { insertion_sort(random_data.dup) }
    end
    
    time_builtin = Benchmark.measure do
      1000.times { random_data.dup.sort }
    end
    
    results[size] = {
      insertion: time_insertion.real,
      builtin: time_builtin.real,
      ratio: time_insertion.real / time_builtin.real
    }
  end
  
  results
end

Common Patterns

Binary Insertion Sort

Optimizing comparisons by using binary search to find insertion position:

def binary_insertion_sort(array)
  (1...array.length).each do |i|
    current = array[i]
    left = 0
    right = i - 1
    
    # Binary search for insertion position
    while left <= right
      mid = (left + right) / 2
      if array[mid] > current
        right = mid - 1
      else
        left = mid + 1
      end
    end
    
    # Shift elements and insert
    position = i - 1
    while position >= left
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[left] = current
  end
  array
end

# Reduces comparisons but not shifts
array = [5, 2, 8, 1, 9]
binary_insertion_sort(array)
# => [1, 2, 5, 8, 9]

Binary insertion sort reduces comparisons from O(n²) to O(n log n) but maintains O(n²) shifts, providing limited practical improvement.

Sentinel Pattern

Using a sentinel value to eliminate boundary checking:

def insertion_sort_with_sentinel(array)
  return array if array.length <= 1
  
  # Find minimum and place it at the start
  min_index = array.each_with_index.min_by { |val, _| val }[1]
  array[0], array[min_index] = array[min_index], array[0]
  
  # Sort remaining elements without boundary check
  (2...array.length).each do |i|
    current = array[i]
    position = i - 1
    
    # No need to check position >= 0 because array[0] is minimum
    while array[position] > current
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[position + 1] = current
  end
  array
end

Stable Sort Guarantee

Ensuring stability when sorting objects with equal comparison values:

class Item
  attr_reader :value, :order
  
  def initialize(value, order)
    @value = value
    @order = order
  end
  
  def <=>(other)
    value <=> other.value
  end
  
  def to_s
    "Item(#{value}, order: #{order})"
  end
end

def stable_insertion_sort(array)
  (1...array.length).each do |i|
    current = array[i]
    position = i - 1
    
    # Use >= comparison to maintain stability
    while position >= 0 && array[position] > current
      array[position + 1] = array[position]
      position -= 1
    end
    
    array[position + 1] = current
  end
  array
end

items = [
  Item.new(3, 1),
  Item.new(1, 2),
  Item.new(3, 3),
  Item.new(2, 4)
]

stable_insertion_sort(items)
# => [Item(1, order: 2), Item(2, order: 4), Item(3, order: 1), Item(3, order: 3)]
# Items with value 3 maintain their original relative order

Early Termination Pattern

Detecting already sorted data to skip unnecessary work:

def insertion_sort_with_early_exit(array)
  already_sorted = true
  
  (1...array.length).each do |i|
    current = array[i]
    
    if array[i - 1] > current
      already_sorted = false
      position = i - 1
      
      while position >= 0 && array[position] > current
        array[position + 1] = array[position]
        position -= 1
      end
      
      array[position + 1] = current
    end
  end
  
  { array: array, was_sorted: already_sorted }
end

Reference

Algorithm Complexity

Performance Characteristics

Operation Counts

Use Case Guidelines

Ruby Method Signatures

Comparison with Other Algorithms

Implementation Variants