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
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.
let instance = Mergesort(),
array = Array.from({length:100}).map(d => Math.random());
instance(array, (a,b) => a - b);npm install @ibowankenobi/mergesortnpm run buildYou will end up with 4 files in the dist folder, an es5 version, an es6 version and minified versions of both.
<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.
If you want to request a particular version, check instructions at jsdelivr.