MergeSort

Mergesort algorithm without recursion, using cached binary trees 👇

Generating a tree beforehand, divides the problem in half, where the first part can be calculated once and reused for arrays with same size.
Lack of recursion avoids functions calls, making the algorithm perform as close as possible to natively compiled vendor implementations.

For larger arrays (> 1M) it performs faster than native solutions (around %25-%50 faster). For smaller arrays performs comparable or slower (around %25 slower).

milliseconds	1M ^*	10M ^**†	100K ^†	100K
Mergesort	34900	229000	11000	10900
Chrome	35200	326000	10200	10200

†: Instance created using size option
*: 50 iterations
**: 30 iterations

Documentation

For a list of config options, see here.

For directly embedding to html, if you are using a browser with compatibility > ie11, use the file ending with ...evergreen.min.js in the dist folder. Otherwise, you can fall back to ...es5.min.js. To read the entire build, refer to the files without the .min. part.

Usage

let instance = Mergesort(),
    array = Array.from({length:100}).map(d => Math.random());

instance(array, (a,b) => a - b);

Installation

npm install @ibowankenobi/mergesort

Build

npm run build

You will end up with 4 files in the dist folder, an es5 version, an es6 version and minified versions of both.

Browser

<script src="https://cdn.jsdelivr.net/npm/ibowankenobi-mergesort"></script>

The contents of the request above is the same as ./dist/mergesort.x.y.z.evergreen.min.js.