// Stable merge sort — CS 499 Enhancement Two.
//
// Why not Array.prototype.sort? Two reasons documented in the code
// review: (1) ECMAScript only guarantees sort stability from ES2019,
// and the artifact targets a range of Node versions; implementing the
// algorithm makes the stability guarantee explicit and testable.
// (2) The enhancement plan requires demonstrating an O(n log n)
// divide-and-conquer sort with a documented complexity analysis.
//
// Complexity: O(n log n) comparisons in all cases (best, average,
// worst), O(n) auxiliary space. Stability matters here because trips
// sorted by price keep their name order within equal prices, which
// makes paginated output deterministic.

/**
 * Sorts an array without mutating it.
 * @param {Array} items - array to sort
 * @param {Function} compare - comparator (a, b) => negative | 0 | positive
 * @returns {Array} new sorted array
 */
function mergeSort(items, compare) {
    if (!Array.isArray(items)) {
        throw new TypeError('mergeSort expects an array');
    }
    if (typeof compare !== 'function') {
        throw new TypeError('mergeSort expects a comparator function');
    }
    if (items.length <= 1) {
        return items.slice();
    }

    const middle = Math.floor(items.length / 2);
    const left = mergeSort(items.slice(0, middle), compare);
    const right = mergeSort(items.slice(middle), compare);
    return merge(left, right, compare);
}

// Merge two sorted arrays. Taking from the LEFT array on ties is what
// makes the sort stable: equal elements keep their original order.
function merge(left, right, compare) {
    const merged = [];
    let i = 0;
    let j = 0;
    while (i < left.length && j < right.length) {
        if (compare(left[i], right[j]) <= 0) {
            merged.push(left[i]);
            i += 1;
        } else {
            merged.push(right[j]);
            j += 1;
        }
    }
    while (i < left.length) {
        merged.push(left[i]);
        i += 1;
    }
    while (j < right.length) {
        merged.push(right[j]);
        j += 1;
    }
    return merged;
}

module.exports = mergeSort;
