/***********************************************************************
  Copyright 2014      (c) Saair Quaderi <saair.quaderi@gmail.com>
  Copyright 2012-2013 (c) Mihai Bazon <mihai.bazon@gmail.com>

  UglyflyJS sourcecode can be found here:
    https://github.com/quaderi/uglyflyjs

  UglyflyJS (by Saair) is a fork of UglifyJS2 (by Mihai Bazon)
  Both libraries are released under the BSD 2-Clause License.
 ***********************************************************************/

/*globals define, module, require */

((typeof define === "function") ? define :
        function () { "use strict"; require('./nd').apply(module, arguments); })(
    "merge_sort",
    [
        //no dependencies
    ],
    function () {
        "use strict";
        function merge_sort(array, cmp) {

            if (array.length < 2) {
                return array.slice();
            }

            function merge(a, b) {
                /*jslint plusplus: true*/
                var r = [],
                    ai = 0,
                    bi = 0,
                    i = 0;
                while (ai < a.length && bi < b.length) {
                    r[i++] = (cmp(a[ai], b[bi]) <= 0) ? a[ai++] : b[bi++];
                }
                if (ai < a.length) {
                    r.push.apply(r, a.slice(ai));
                }
                if (bi < b.length) {
                    r.push.apply(r, b.slice(bi));
                }
                return r;
            }

            function ms(a) {
                var m,
                    left,
                    right;
                if (a.length <= 1) {
                    return a;
                }
                m = Math.floor(a.length / 2);
                left = a.slice(0, m);
                right = a.slice(m);
                left = ms(left);
                right = ms(right);
                return merge(left, right);
            }

            return ms(array);
        }
        return merge_sort;
    }
);