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

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

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

Installation

`javascript
npm install @ibowankenobi/mergesort
`

Build

`javascript
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

`javascript

`

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

If you want to request a particular version, check instructions at jsdelivr.