Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Ruby DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.rb 
arr = [5, 1, 4, 2, 8]
(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
puts arr.inspect

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • arr is a Ruby Array, and the source mutates it in place with indexed assignments like arr[j + 1] = arr[j].
  • The outer loop is (1...arr.length).each, so each i starts at the first unsorted slot and stops before arr.length.
  • key = arr[i] saves the current value before larger earlier values are shifted over it.
  • j = i - 1 walks left through the sorted prefix while j >= 0 && arr[j] > key.
  • The j >= 0 check prevents Ruby negative indexes from wrapping around to the end of the array during this scan.
  • After any shifts, arr[j + 1] = key writes the saved value into its final slot.
  • The trace shows [5, 1, 4, 2, 8] become [1, 5, 4, 2, 8], then [1, 4, 5, 2, 8], then [1, 2, 4, 5, 8].
  • puts arr.inspect prints the final Ruby array literal shape: [1, 2, 4, 5, 8].
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.