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.

Merge Sort

Animation, code, analysis, and discussion of merge 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

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

DISCUSSION

Merge sort is very predictable. It makes between 0.5lg(n) and lg(n) comparisons per element, and between lg(n) and 1.5lg(n) swaps per element. The minima are achieved for already sorted data; the maxima are achieved, on average, for random data. If using Θ(n) extra space is of no concern, then merge sort is an excellent choice: It is simple to implement, and it is the only stable O(n·lg(n)) sorting algorithm. Note that when sorting linked lists, merge sort requires only Θ(lg(n)) extra space (for recursion).

Merge sort is the algorithm of choice for a variety of situations: when stability is required, when sorting linked lists, and when random access is much more expensive than sequential access (for example, external sorting on tape).

There do exist linear time in-place merge algorithms for the last step of the algorithm, but they are both expensive and complex. The complexity is justified for applications such as external sorting when Θ(n) extra space is not available.

KEY

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.
  • Dark gray values denote the current interval.

PROPERTIES

  • Stable
  • Θ(n) extra space for arrays (as shown)
  • Θ(lg(n)) extra space for linked lists
  • Θ(n·lg(n)) time
  • Not adaptive
  • Does not require random access to data

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