Merge sort uses divide and conquer technique to provide fast and stable sorting.


How merge sort works

It divides the array in half recursively until to single item. Then merges two sorted arrays until all elements are sorted.

merge sort

The merge method is to compare each element in two sorted array one by one, put the smaller one in the third array until one of arrays reaches the end. Then copy the rest of unfinished array to the third array. This requires an additional array in memory, equal in size to the one being sorted.

Merge sort is an efficient sorting technique. It has O(nlogn) complexity. The downside is that it requires extra space for the additional array. The space complexity is O(n).


Implement merge sort

Java

Javascript

Python

Doodle

mergesort doodle


Download

Download merge sort Java, JavaScript and Python code
Sorting doodles compilation (YouTube)

What are the pros and cons of merge sort compared to quicksort?

Both merge sort and quicksort use divide and conquer technique. Merge sort uses extra space O(n) for storage of sub-array, while quicksort doesn’t. Merge sort is more stable than quicksort.