{"version":3,"file":"sort-812cc211.cjs","sources":["../sort.js"],"sourcesContent":["/**\n * Efficient sort implementations.\n *\n * Note: These sort implementations were created to compare different sorting algorithms in JavaScript.\n * Don't use them if you don't know what you are doing. Native Array.sort is almost always a better choice.\n *\n * @module sort\n */\n\nimport * as math from './math.js'\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {number} lo\n * @param {number} hi\n * @param {function(T,T):number} compare\n */\nexport const _insertionSort = (arr, lo, hi, compare) => {\n  for (let i = lo + 1; i <= hi; i++) {\n    for (let j = i; j > 0 && compare(arr[j - 1], arr[j]) > 0; j--) {\n      const tmp = arr[j]\n      arr[j] = arr[j - 1]\n      arr[j - 1] = tmp\n    }\n  }\n}\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {function(T,T):number} compare\n * @return {void}\n */\nexport const insertionSort = (arr, compare) => {\n  _insertionSort(arr, 0, arr.length - 1, compare)\n}\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {number} lo\n * @param {number} hi\n * @param {function(T,T):number} compare\n */\nconst _quickSort = (arr, lo, hi, compare) => {\n  if (hi - lo < 42) {\n    _insertionSort(arr, lo, hi, compare)\n  } else {\n    const pivot = arr[math.floor((lo + hi) / 2)]\n    let i = lo\n    let j = hi\n    while (true) {\n      while (compare(pivot, arr[i]) > 0) {\n        i++\n      }\n      while (compare(arr[j], pivot) > 0) {\n        j--\n      }\n      if (i >= j) {\n        break\n      }\n      // swap arr[i] with arr[j]\n      // and increment i and j\n      const arri = arr[i]\n      arr[i++] = arr[j]\n      arr[j--] = arri\n    }\n    _quickSort(arr, lo, j, compare)\n    _quickSort(arr, j + 1, hi, compare)\n  }\n}\n\n/**\n * This algorithm beats Array.prototype.sort in Chrome only with arrays with 10 million entries.\n * In most cases [].sort will do just fine. Make sure to performance test your use-case before you\n * integrate this algorithm.\n *\n * Note that Chrome's sort is now a stable algorithm (Timsort). Quicksort is not stable.\n *\n * @template T\n * @param {Array<T>} arr\n * @param {function(T,T):number} compare\n * @return {void}\n */\nexport const quicksort = (arr, compare) => {\n  _quickSort(arr, 0, arr.length - 1, compare)\n}\n"],"names":["math.floor"],"mappings":";;;;AAAA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AAGA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,cAAc,GAAG,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,KAAK;AACxD,EAAE,KAAK,IAAI,CAAC,GAAG,EAAE,GAAG,CAAC,EAAE,CAAC,IAAI,EAAE,EAAE,CAAC,EAAE,EAAE;AACrC,IAAI,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,IAAI,OAAO,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,EAAE,GAAG,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;AACnE,MAAM,MAAM,GAAG,GAAG,GAAG,CAAC,CAAC,EAAC;AACxB,MAAM,GAAG,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC,CAAC,GAAG,CAAC,EAAC;AACzB,MAAM,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,IAAG;AACtB,KAAK;AACL,GAAG;AACH,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,aAAa,GAAG,CAAC,GAAG,EAAE,OAAO,KAAK;AAC/C,EAAE,cAAc,CAAC,GAAG,EAAE,CAAC,EAAE,GAAG,CAAC,MAAM,GAAG,CAAC,EAAE,OAAO,EAAC;AACjD,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA,MAAM,UAAU,GAAG,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,KAAK;AAC7C,EAAE,IAAI,EAAE,GAAG,EAAE,GAAG,EAAE,EAAE;AACpB,IAAI,cAAc,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,EAAC;AACxC,GAAG,MAAM;AACT,IAAI,MAAM,KAAK,GAAG,GAAG,CAACA,UAAU,CAAC,CAAC,EAAE,GAAG,EAAE,IAAI,CAAC,CAAC,EAAC;AAChD,IAAI,IAAI,CAAC,GAAG,GAAE;AACd,IAAI,IAAI,CAAC,GAAG,GAAE;AACd,IAAI,OAAO,IAAI,EAAE;AACjB,MAAM,OAAO,OAAO,CAAC,KAAK,EAAE,GAAG,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE;AACzC,QAAQ,CAAC,GAAE;AACX,OAAO;AACP,MAAM,OAAO,OAAO,CAAC,GAAG,CAAC,CAAC,CAAC,EAAE,KAAK,CAAC,GAAG,CAAC,EAAE;AACzC,QAAQ,CAAC,GAAE;AACX,OAAO;AACP,MAAM,IAAI,CAAC,IAAI,CAAC,EAAE;AAClB,QAAQ,KAAK;AACb,OAAO;AACP;AACA;AACA,MAAM,MAAM,IAAI,GAAG,GAAG,CAAC,CAAC,EAAC;AACzB,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,GAAG,CAAC,CAAC,EAAC;AACvB,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,KAAI;AACrB,KAAK;AACL,IAAI,UAAU,CAAC,GAAG,EAAE,EAAE,EAAE,CAAC,EAAE,OAAO,EAAC;AACnC,IAAI,UAAU,CAAC,GAAG,EAAE,CAAC,GAAG,CAAC,EAAE,EAAE,EAAE,OAAO,EAAC;AACvC,GAAG;AACH,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,SAAS,GAAG,CAAC,GAAG,EAAE,OAAO,KAAK;AAC3C,EAAE,UAAU,CAAC,GAAG,EAAE,CAAC,EAAE,GAAG,CAAC,MAAM,GAAG,CAAC,EAAE,OAAO,EAAC;AAC7C;;;;;;;;;;;;;;"}