归并排序 #

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
  function merge(left, right) {
    const result = [];
    while (left.length && right.length) {
      if (left[0] <= right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    while (left.length) {
      result.push(left.shift());
    }
    while (right.length) {
      result.push(right.shift());
    }
    return result;
  }
}

const { mergeSort } = require('./mergeSort');
describe('mergeSort', () => {
  it('case1', () => {
    const nums = [3, 2, 5, 7, 8, 9, 0, 6];
    const expected = [0, 2, 3, 5, 6, 7, 8, 9];
    expect(mergeSort(nums)).toEqual(expected);
  });
  it('case2', () => {
    const nums = [];
    const expected = [];
    expect(mergeSort(nums)).toEqual(expected);
  });
  it('case3', () => {
    const nums = [1];
    const expected = [1];
    expect(mergeSort(nums)).toEqual(expected);
  });
  it('case4', () => {
    const nums = [1, 2];
    const expected = [1, 2];
    expect(mergeSort(nums)).toEqual(expected);
  });
});