Skills in High Demand
by Toptal Clients
React.js Developer JobsNode.js Developer JobsRuby on Rails Developer JobsAzure Developer JobsReact Native Developer JobsQA Engineer JobsGo Engineer JobsJavaScript Developer JobsPython Developer JobsDjango Developer JobsPHP Developer JobsC# Developer JobsiOS Developer JobsBlockchain Developer JobsSwift Developer JobsAWS Developer JobsVue.js Developer JobsJava Developer Jobs.NET Developer JobsAngular Developer JobsAndroid Developer JobsMagento Developer JobsShopify Developer JobsWordPress Developer JobsLaravel Developer JobsElixir Developer JobsDocker Developer JobsFlutter Developer JobsSoftware Architect JobsUnity or Unity3D Developer JobsCloud Engineer JobsASP.NET Developer JobsKubernetes Expert JobsSystem Security Developer JobsKotlin Developer JobsCSS Developer JobsComputer Vision Developer JobsAI Engineer JobsDrupal Developer JobsSQL Developer JobsSymfony Developer JobsRuby Developer JobsData Scientist JobsBusiness Intelligence Developer JobsC++ Developer JobsIonic Developer JobsGraphQL Developer JobsMachine Learning Engineer JobsXamarin Developer JobsFirebase Developer JobsReact.js Developer JobsNode.js Developer JobsRuby on Rails Developer JobsAzure Developer JobsReact Native Developer JobsQA Engineer JobsGo Engineer JobsJavaScript Developer JobsPython Developer JobsDjango Developer JobsPHP Developer JobsC# Developer JobsiOS Developer JobsBlockchain Developer JobsSwift Developer JobsAWS Developer JobsVue.js Developer JobsJava Developer Jobs.NET Developer JobsAngular Developer JobsAndroid Developer JobsMagento Developer JobsShopify Developer JobsWordPress Developer JobsLaravel Developer JobsElixir Developer JobsDocker Developer JobsFlutter Developer JobsSoftware Architect JobsUnity or Unity3D Developer JobsCloud Engineer JobsASP.NET Developer JobsKubernetes Expert JobsSystem Security Developer JobsKotlin Developer JobsCSS Developer JobsComputer Vision Developer JobsAI Engineer JobsDrupal Developer JobsSQL Developer JobsSymfony Developer JobsRuby Developer JobsData Scientist JobsBusiness Intelligence Developer JobsC++ Developer JobsIonic Developer JobsGraphQL Developer JobsMachine Learning Engineer JobsXamarin Developer JobsFirebase Developer Jobs

Toptal connects the top 3% of freelance developers all over the world.

Insertion Sort

Animation, code, analysis, and discussion of insertion sort on 4 initial conditions.

How to use: Press "Play all", or choose the  Play  button.

Play All
Play animation
Random
Play animation
Nearly Sorted
Play animation
Reversed
Play animation
Few Unique

ALGORITHM

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

DISCUSSION

Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

KEY

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.

PROPERTIES

  • Stable
  • O(1) extra space
  • O(n2) comparisons and swaps
  • Adaptive: O(n) time when nearly sorted
  • Very low overhead

Preparing for a technical interview? Check out our interview guides.