ibowankenobi-mergesort
v0.0.3
Published
Merge Sort algorithm implementation without recursion, using cached binary trees
Downloads
5
Maintainers
Readme
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
.
If you want to request a particular version, check instructions at jsdelivr.