Skip to content

Merge Sort algorithm implementation without recursion, using cached binary trees

License

Notifications You must be signed in to change notification settings

IbrahimTanyalcin/MergeSort

Repository files navigation

MergeSort

Codacy Badge DOI

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.

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.