JavaScript で非同期関数を使った sort

プロダクション環境で使われるようなものかは分からないけれども、趣味プロをしていた時に欲しくなったものを、備忘録的に残しておきます。

Array.prototype.sort の引数には、同期で結果を返す関数しか渡せません。
しかし、時には値の比較を非同期に行いたいこともあるのではないでしょうか。

そんな時は、 native の関数は使えないので、自前で sort を実装してしまいましょう。

/**
 * return the mid value among x, y, and z
 * @param x
 * @param y
 * @param z
 * @param compare
 * @returns {Promise.<*>}
 */
async function getPivot(x, y, z, compare) {
  if (await compare(x, y) < 0) {
    if (await compare(y, z) < 0) {
      return y;
    } else if (await compare(z, x) < 0) {
      return x;
    } else {
      return z;
    }
  } else if (await compare(y, z) > 0) {
    return y;
  } else if (await compare(z, x) > 0) {
    return x;
  } else {
    return z;
  }
}

/**
 * asynchronous quick sort
 * @param arr array to sort
 * @param compare asynchronous comparing function
 * @param left index where the range of elements to be sorted starts
 * @param right index where the range of elements to be sorted ends
 * @returns {Promise.<*>}
 */
async function quickSort(arr, compare, left = 0, right = arr.length - 1) {
  if (left < right) {
    let i = left, j = right, tmp;
    const pivot = await getPivot(arr[i], arr[i + Math.floor((j - i) / 2)], arr[j], compare);
    while (true) {
      while (await compare(arr[i],  pivot) < 0) {
        i++;
      }
      while (await compare(pivot, arr[j]) < 0) {
        j--;
      }
      if (i >= j) {
        break;
      }
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;

      i++;
      j--;
    }
    await quickSort(arr, compare, left, i - 1);
    await quickSort(arr, compare, j + 1, right);
  }
  return arr;
}

// example usage
quickSort(array, (a, b) => Promise.resolve(a - b));

Wikipedia の quickSort のコードを元に書いてみました。
aync/await を使うと、非同期を意識せずにシンプルに書けますね。
こういうの、もし需要があるなら、すでに npm に publish されてそうですが、あまりちゃんと調べません。。