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 temp = new Array(n);
  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, i);
        if (arr[j] <= key) break;
        arr[j + 1] = arr[j];
        write(j + 1, arr[j + 1]);
        j--;
      }
      arr[j + 1] = key;
      write(j + 1, key);
    }
  }
  function merge(lo, mid, hi) {
    let i = lo;
    let j = mid + 1;
    let k = lo;
    while (i <= mid && j <= hi) {
      compare(i, j);
      if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    for (let p = lo; p <= hi; p++) {
      arr[p] = temp[p];
      write(p, arr[p]);
    }
  }
  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) merge(lo, mid, hi);
    }
  }
} def sort(arr, n, stats):
    temp = [0] * n
    run = 16
    def insertion(lo, hi):
        for i in range((lo + 1), hi + 1):
            key = arr[i]
            j = (i - 1)
            while (j >= lo):
                if (arr[j] <= key):
                    break
                arr[(j + 1)] = arr[j]
                j -= 1
            arr[(j + 1)] = key
    def merge(lo, mid, hi):
        i = lo
        j = (mid + 1)
        k = lo
        while ((i <= mid) and (j <= hi)):
            if (arr[i] <= arr[j]):
                temp[k] = arr[i]
                k += 1
                i += 1
            else:
                temp[k] = arr[j]
                k += 1
                j += 1
        while (i <= mid):
            temp[k] = arr[i]
            k += 1
            i += 1
        while (j <= hi):
            temp[k] = arr[j]
            k += 1
            j += 1
        for p in range(lo, hi + 1):
            arr[p] = temp[p]
    i = 0
    while (i < n):
        insertion(i, min(((i + run) - 1), (n - 1)))
        i += run
    width = run
    while (width < n):
        i = 0
        while (i < n):
            lo = i
            mid = min(((i + width) - 1), (n - 1))
            hi = min(((i + (width << 1)) - 1), (n - 1))
            if (mid < hi):
                merge(lo, mid, hi)
            i += (width << 1)
        width <<= 1 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            if((arr[i] <= arr[j])) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    std::vector<int> temp(n);
    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)) {
                merge(lo, mid, hi);
            }
        }
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            if((arr[i] <= arr[j])) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    int[] temp = new int[n];
    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)) {
                merge(lo, mid, hi);
            }
        }
    }
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            if((arr[i] <= arr[j])) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    int temp[n];
    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)) {
                merge(lo, mid, hi);
            }
        }
    }
} 