WikiSort — VisualAlgorithms Docs

How it works

Stable in-place merge sort in the WikiSort family: builds short runs with insertion sort, then repeatedly merges adjacent runs in place using rotations and shifts rather than an auxiliary buffer.
Implementation

      
 function wikiSort(arr, stats) {
  const n = arr.length;
  const run = 16;
  function insertion(lo, hi) {
    for (let i = lo + 1; i <= hi; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= lo) {
        compare(j, j + 1);
        if (arr[j] <= key) break;
        arr[j + 1] = arr[j];
        swap(j + 1, j);
        j--;
      }
      arr[j + 1] = key;
    }
  }
  function mergeInPlace(lo, mid, hi) {
    if (lo > mid || mid >= hi) return;
    compare(mid, mid + 1);
    if (arr[mid] <= arr[mid + 1]) return;
    let i = lo;
    let j = mid + 1;
    while (i < j && j <= hi) {
      compare(i, j);
      if (arr[i] <= arr[j]) {
        i++;
      } else {
        const val = arr[j];
        let k = j;
        while (k > i) {
          arr[k] = arr[k - 1];
          swap(k, k - 1);
          k--;
        }
        arr[i] = val;
        i++;
        j++;
      }
    }
  }
  for (let i = 0; i < n; i += run) insertion(i, Math.min(i + run - 1, n - 1));
  for (let width = run; width < n; width <<= 1) {
    for (let i = 0; i < n; i += width << 1) {
      const lo = i;
      const mid = Math.min(i + width - 1, n - 1);
      const hi = Math.min(i + (width << 1) - 1, n - 1);
      if (mid < hi) mergeInPlace(lo, mid, hi);
    }
    checkpoint(Math.min(width << 1, n), n);
  }
  for (let i = 0; i < n; i++) markSorted(i);
}
 def wikiSort(arr, stats):
    def insertion(lo, hi):
        for i in range((lo + 1), (hi + 1)):
            key = arr[i]
            j = (i - 1)
            while (j >= lo):
                compare(j, (j + 1))
                if (arr[j] <= key):
                    break
                arr[(j + 1)] = arr[j]
                swap((j + 1), j)
                j -= 1
            arr[(j + 1)] = key

    def mergeInPlace(lo, mid, hi):
        if ((lo > mid) or (mid >= hi)):
            return
        compare(mid, (mid + 1))
        if (arr[mid] <= arr[(mid + 1)]):
            return
        i = lo
        j = (mid + 1)
        while ((i < j) and (j <= hi)):
            compare(i, j)
            if (arr[i] <= arr[j]):
                i += 1
            else:
                val = arr[j]
                k = j
                while (k > i):
                    arr[k] = arr[(k - 1)]
                    swap(k, (k - 1))
                    k -= 1
                arr[i] = val
                i += 1
                j += 1

    run = 16
    for i in range(0, n, run):
        insertion(i, (((i + run) - 1) if ((i + run) - 1) <= (n - 1) else (n - 1)))
    width = run
    while (width < n):
        for i in range(0, n, (width << 1)):
            lo = i
            mid = (((i + width) - 1) if ((i + width) - 1) <= (n - 1) else (n - 1))
            hi = (((i + (width << 1)) - 1) if ((i + (width << 1)) - 1) <= (n - 1) else (n - 1))
            if (mid < hi):
                mergeInPlace(lo, mid, hi)
        checkpoint(((width << 1) if (width << 1) <= n else n), n)
        width <<= 1
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void insertion(int lo, int hi);
void mergeInPlace(int lo, int mid, int hi);

void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            swap((j + 1), j);
            j--;
        }
        arr[(j + 1)] = key;
    }
}

void mergeInPlace(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int i = lo;
    int j = (mid + 1);
    while(((i < j) && (j <= hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            i++;
        } else {
            int val = arr[j];
            int k = j;
            while((k > i)) {
                arr[k] = arr[(k - 1)];
                swap(k, (k - 1));
                k--;
            }
            arr[i] = val;
            i++;
            j++;
        }
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int run = 16;
    for(int i=0; i<n; i+=run) {
        insertion(i, ((((i + run) - 1)) < ((n - 1)) ? (((i + run) - 1)) : ((n - 1))));
    }
    for(int width=run; (width < n); width <<= 1) {
        for(int i=0; i<n; i+=(width << 1)) {
            int lo = i;
            int mid = ((((i + width) - 1)) < ((n - 1)) ? (((i + width) - 1)) : ((n - 1)));
            int hi = ((((i + (width << 1)) - 1)) < ((n - 1)) ? (((i + (width << 1)) - 1)) : ((n - 1)));
            if((mid < hi)) {
                mergeInPlace(lo, mid, hi);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            swap((j + 1), j);
            j--;
        }
        arr[(j + 1)] = key;
    }
}

void mergeInPlace(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int i = lo;
    int j = (mid + 1);
    while(((i < j) && (j <= hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            i++;
        } else {
            int val = arr[j];
            int k = j;
            while((k > i)) {
                arr[k] = arr[(k - 1)];
                swap(k, (k - 1));
                k--;
            }
            arr[i] = val;
            i++;
            j++;
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    int run = 16;
    for(int i=0; i<n; i+=run) {
        insertion(i, Math.Min(((i + run) - 1), (n - 1)));
    }
    for(int width=run; (width < n); width <<= 1) {
        for(int i=0; i<n; i+=(width << 1)) {
            int lo = i;
            int mid = Math.Min(((i + width) - 1), (n - 1));
            int hi = Math.Min(((i + (width << 1)) - 1), (n - 1));
            if((mid < hi)) {
                mergeInPlace(lo, mid, hi);
            }
        }
        checkpoint(Math.Min((width << 1), n), n);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void insertion(int lo, int hi);
void mergeInPlace(int lo, int mid, int hi);

void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            swap((j + 1), j);
            j--;
        }
        arr[(j + 1)] = key;
    }
}

void mergeInPlace(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int i = lo;
    int j = (mid + 1);
    while(((i < j) && (j <= hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            i++;
        } else {
            int val = arr[j];
            int k = j;
            while((k > i)) {
                arr[k] = arr[(k - 1)];
                swap(k, (k - 1));
                k--;
            }
            arr[i] = val;
            i++;
            j++;
        }
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int run = 16;
    for(int i=0; i<n; i+=run) {
        insertion(i, ((((i + run) - 1)) < ((n - 1)) ? (((i + run) - 1)) : ((n - 1))));
    }
    for(int width=run; (width < n); width <<= 1) {
        for(int i=0; i<n; i+=(width << 1)) {
            int lo = i;
            int mid = ((((i + width) - 1)) < ((n - 1)) ? (((i + width) - 1)) : ((n - 1)));
            int hi = ((((i + (width << 1)) - 1)) < ((n - 1)) ? (((i + (width << 1)) - 1)) : ((n - 1)));
            if((mid < hi)) {
                mergeInPlace(lo, mid, hi);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 