JavaScript is required for this website. Please allow JavaScript and refresh the page.
home Home
sort Sorts
LOGARITHMIC
Quick Sort Merge Sort Heap Sort
QUADRATIC
Bubble Sort Selection Sort Insertion Sort Gnome Sort Shaker Sort Odd Even Sort Pancake Sort
WEIRD
Bitonic Sort Radix Sort Shell Sort Comb Sort Bogo Sort
CUSTOM
Your Sort
SORT VISUALIZER
Insertion Sort
Elements: 100
DESCRIPTION

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It's less performant than advanced sorting algorithms, but it can still have some advantages: it's really easy to implement and it's efficient on small data structures almost sorted.

The algorithm divides the data structure in two sublists: a sorted one, and one still to sort. Initially, the sorted sublist is made up of just one element and it gets progressively filled. For every iteration, the algorithm picks an element on the unsorted sublist and inserts it at the right place in the sorted sublist. It's available in several variants such as Gnome Sort.

COMPLEXITY
Average Complexity O(n2)
Best Case O(n)
Worst Case O(n2)
Space Complexity O(1)