Merge Sort

Definition

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/src/algorithms/sorting/merge_sort.js

Test: https://github.com/felipernb/algorithms.js/blob/master/test/algorithms/sorting/merge_sort.js

Algorithm

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

How to use

Import

var mergeSort = require('algorithms').Sort.mergeSort;

Calling

var a = [2,5,1,4,3,6,20,-10];
mergeSort(a);
console.info(a); // [-10,1,3,4,5,6,20]

And in case a custom comparing function should be called, this Merge Sort implementation uses a Comparator, that can be used like this:

var a = [2,5,1,4,3,6,20,-10];
// Comparator function
var reverseOrder = function (a, b) {
  if (a == b) return 0;
  return a > b ? -1 : 1;
};

console.info(mergeSort(a, reverseOrder); // [20,6,5,4,3,1,-10]