Slowsort

Multiply and surrender.

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

How it works

Multiply and surrender.

Implementation

      
 function slowSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  let mid = Math.floor((lo + hi) / 2);
  slowSort(arr, lo, mid);
  slowSort(arr, mid + 1, hi);
  if (arr[hi] < arr[mid])
    [arr[hi], arr[mid]] = [arr[mid], arr[hi]];
  slowSort(arr, lo, hi - 1);
} def slow_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    mid = (lo + hi) // 2
    slow_sort(arr, lo, mid)
    slow_sort(arr, mid + 1, hi)
    if arr[hi] < arr[mid]:
        arr[hi], arr[mid] = arr[mid], arr[hi]
    slow_sort(arr, lo, hi - 1) void slowSort(vector<int>& arr, int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  slowSort(arr, lo, mid);
  slowSort(arr, mid + 1, hi);
  if (arr[hi] < arr[mid]) swap(arr[hi], arr[mid]);
  slowSort(arr, lo, hi - 1);
} void SlowSort(int[] arr, int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  SlowSort(arr, lo, mid);
  SlowSort(arr, mid + 1, hi);
  if (arr[hi] < arr[mid])
    (arr[hi], arr[mid]) = (arr[mid], arr[hi]);
  SlowSort(arr, lo, hi - 1);
} void slowSort(int arr[], int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  slowSort(arr, lo, mid);
  slowSort(arr, mid + 1, hi);
  if (arr[hi] < arr[mid]) {
    int t = arr[hi]; arr[hi] = arr[mid]; arr[mid] = t;
  }
  slowSort(arr, lo, hi - 1);
} 