Insertion sort
Sort an integer array in ascending order using insertion sort.
Course progress
Problem 22 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [5, 2, 4, 6, 1, 3]
Expected output
1 2 3 4 5 6
What is happening?
Each new value is inserted into its correct place in the already-sorted prefix until the full array becomes 1 through 6.
Solution strategy
Build the right mental model
Grow a sorted prefix. Remove the next value, shift larger prefix values one position right, and insert the value into the gap.
Core concepts
sorting · array shifting
Complexity
Time O(n^2), space O(1). Nearly sorted input approaches O(n) time.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for insertion-sort
using System;
class Program
{
static void InsertionSort(int[] numbers)
{
for (int i = 1; i < numbers.Length; i++)
{
int value = numbers[i];
int position = i - 1;
while (position >= 0 && numbers[position] > value)
{
numbers[position + 1] = numbers[position];
position--;
}
numbers[position + 1] = value;
}
}
static void Main()
{
int[] values = { 5, 2, 4, 6, 1, 3 };
InsertionSort(values);
Console.WriteLine(string.Join(" ", values));
}
}Knowledge check
Questions students often ask
What is the main idea behind insertion sort?
Grow a sorted prefix. Remove the next value, shift larger prefix values one position right, and insert the value into the gap.
What is the time and space complexity of this solution?
Time O(n^2), space O(1). Nearly sorted input approaches O(n) time.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.