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.

Sorting Algorithms Animations

The following animations illustrate how effectively data sets from different starting points can be sorted using different algorithms.

How to use: Press "Play all", or choose the  Play  button for the individual row/column to animate.

Try me!
Play AllInsertionSelectionBubbleShellMergeHeapQuickQuick3
Random
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Nearly Sorted
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Reversed
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Few Unique
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play animation
Play AllRandomNearly SortedReversedFew Unique
Insertion
Play animation
Play animation
Play animation
Play animation
Selection
Play animation
Play animation
Play animation
Play animation
Bubble
Play animation
Play animation
Play animation
Play animation
Shell
Play animation
Play animation
Play animation
Play animation
Merge
Play animation
Play animation
Play animation
Play animation
Heap
Play animation
Play animation
Play animation
Play animation
Quick
Play animation
Play animation
Play animation
Play animation
Quick3
Play animation
Play animation
Play animation
Play animation

INITIAL CONDITION:

PROBLEM SIZE:

KEY

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.
  • Dark gray values denote the current interval (shell, merge, quick).
  • A pair of red triangles marks the left and right pointers (quick).

DISCUSSION

These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to:

  • Show how each algorithm operates.
  • Show that there is no best sorting algorithm.
  • Show the advantages and disadvantages of each algorithm.
  • Show that worse-case asymptotic behavior is not always the deciding factor in choosing an algorithm.
  • Show that the initial condition (input order and key distribution) affects performance as much as the algorithm choice.

The ideal sorting algorithm would have the following properties:

  • Stable: Equal keys aren’t reordered.
  • Operates in place, requiring O(1) extra space.
  • Worst-case O(n·lg(n)) key comparisons.
  • Worst-case O(n) swaps.
  • Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

Sorting is a vast topic; this site explores the topic of in-memory generic algorithms for arrays. External sorting, radix sorting, string sorting, and linked list sorting—all wonderful and interesting topics—are deliberately omitted to limit the scope of discussion.

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

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code by Discussion.

Bubble-sort with Hungarian (“Csángó”) folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.