1. Docs
  2. /
  3. Sorting
  4. /
  5. 3-Way Merge Sort

3-Way Merge Sort

Splits into three parts instead of two. Slightly fewer comparisons than standard merge sort in theory.

Best O(n log₃ n) Avg O(n log₃ n) Worst O(n log₃ n) Space O(n) Stable Yes In-place No Comparison-based

How it works

Splits into three parts instead of two. Slightly fewer comparisons than standard merge sort in theory.

Implementation

function merge3Sort(arr, lo = 0, hi = arr.length) {
  if (hi - lo < 2) return;
  const t = Math.max(1, Math.floor((hi - lo) / 3));
  merge3Sort(arr, lo, lo + t);
  merge3Sort(arr, lo + t, lo + 2*t);
  merge3Sort(arr, lo + 2*t, hi);
  // 3-way merge of three sorted runs
  const a = arr.slice(lo, lo+t);
  const b = arr.slice(lo+t, lo+2*t);
  const c = arr.slice(lo+2*t, hi);
  // merge a, b, c back into arr[lo..hi]
}