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.

Quick Sort 3 Way

Animation, code, analysis, and discussion of quick sort (3 way partition) 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

_# choose pivot_
swap a[n,rand(1,n)]

_# 3-way partition_
i = 1, k = 1, p = n
while i < p,
  if a[i] < a[n], swap a[i++,k++]
  else if a[i] == a[n], swap a[i,--p]
  else i++
end
_→ invariant: a[p..n] all equal_
_→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]_

_# move pivots to center_
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

_# recursive sorts_
sort a[1..k-1]
sort a[n-p+k+1,n]

DISCUSSION

The 3-way partition variation of quick sort has slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst case time bounds, but this version is highly adaptive in the very common case of sorting with few unique keys.

The 3-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, and performs more swaps than necessary. A more efficient but more elaborate 3-way partitioning method is given in Quicksort is Optimal by Robert Sedgewick and Jon Bentley.

When stability is not required, quick sort is the general purpose sorting algorithm of choice. Recently, a novel dual-pivot variant of 3-way partitioning has been discovered that beats the single-pivot 3-way partitioning method both in theory and in practice.

KEY

  • Black values are sorted.
  • Gray values are unsorted.
  • Dark gray values denote the current interval.
  • A pair of red triangles mark k and p (see the code).

PROPERTIES

  • Not stable
  • O(lg(n)) extra space
  • O(n2) time, but typically O(n·lg(n)) time
  • Adaptive: O(n) time when O(1) unique keys

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