Sqrt Sort — VisualAlgorithms Docs

How it works

Hybrid stable approach using square-root-sized buffers and blockwise merging.
Implementation

      
 function sqrtSort(arr, stats) {
  const n = arr.length;
  const block = Math.max(2, Math.floor(Math.sqrt(n || 1)));
  const buf = new Array(block);
  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 reverseRange(start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      swap(start, end);
      start++;
      end--;
    }
  }
  function rotate(lo, mid, hi) {
    if (lo > mid || mid >= hi) return;
    reverseRange(lo, mid);
    reverseRange(mid + 1, hi);
    reverseRange(lo, hi);
  }
  function lowerBound(lo, hi, target) {
    while (lo <= hi) {
      const m = lo + (hi - lo >> 1);
      compare(m, m);
      if (arr[m] < target) lo = m + 1; else hi = m - 1;
    }
    return lo;
  }
  function upperBound(lo, hi, target) {
    while (lo <= hi) {
      const m = lo + (hi - lo >> 1);
      compare(m, m);
      if (arr[m] <= target) lo = m + 1; else hi = m - 1;
    }
    return lo;
  }
  function merge(lo, mid, hi) {
    if (lo > mid || mid >= hi) return;
    compare(mid, mid + 1);
    if (arr[mid] <= arr[mid + 1]) return;
    let leftLen = mid - lo + 1;
    let rightLen = hi - mid;
    if (leftLen <= block) {
      for (let i = 0; i < leftLen; i++) buf[i] = arr[lo + i];
      let bi = 0, ri = mid + 1, wi = lo;
      while (bi < leftLen && ri <= hi) {
        compare(wi, ri);
        if (buf[bi] <= arr[ri]) {
          arr[wi] = buf[bi++];
        } else {
          arr[wi] = arr[ri++];
        }
        write(wi, arr[wi]);
        wi++;
      }
      while (bi < leftLen) {
        arr[wi] = buf[bi++];
        write(wi, arr[wi]);
        wi++;
      }
      return;
    }
    if (rightLen <= block) {
      for (let i = 0; i < rightLen; i++) buf[i] = arr[mid + 1 + i];
      let li = mid, bi = rightLen - 1, wi = hi;
      while (li >= lo && bi >= 0) {
        if (arr[li] > buf[bi]) {
          arr[wi] = arr[li--];
        } else {
          arr[wi] = buf[bi--];
        }
        write(wi, arr[wi]);
        wi--;
      }
      while (bi >= 0) {
        arr[wi] = buf[bi--];
        write(wi, arr[wi]);
        wi--;
      }
      return;
    }
    let halfLeft = Math.floor(leftLen / 2);
    let splitL = lo + halfLeft;
    let splitR = lowerBound(mid + 1, hi, arr[splitL]);
    let newMid = splitL + (splitR - mid - 1);
    rotate(splitL, mid, splitR - 1);
    merge(lo, splitL - 1, newMid - 1);
    merge(newMid, splitR - 1, hi);
  }
  for (let i = 0; i < n; i += block) insertion(i, Math.min(i + block - 1, n - 1));
  for (let width = block; 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);
    }
    checkpoint(Math.min(width << 1, n), n);
  }
}
 def sqrtSort(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 reverseRange(start, end):
        while (start < end):
            arr[start], arr[end] = arr[end], arr[start]
            swap(start, end)
            start += 1
            end -= 1

    def rotate(lo, mid, hi):
        if ((lo > mid) or (mid >= hi)):
            return
        reverseRange(lo, mid)
        reverseRange((mid + 1), hi)
        reverseRange(lo, hi)

    def lowerBound(lo, hi, target):
        while (lo <= hi):
            m = (lo + ((hi - lo) >> 1))
            compare(m, m)
            if (arr[m] < target):
                lo = (m + 1)
            else:
                hi = (m - 1)
        return lo

    def upperBound(lo, hi, target):
        while (lo <= hi):
            m = (lo + ((hi - lo) >> 1))
            compare(m, m)
            if (arr[m] <= target):
                lo = (m + 1)
            else:
                hi = (m - 1)
        return lo

    def merge(lo, mid, hi):
        if ((lo > mid) or (mid >= hi)):
            return
        compare(mid, (mid + 1))
        if (arr[mid] <= arr[(mid + 1)]):
            return
        leftLen = ((mid - lo) + 1)
        rightLen = (hi - mid)
        if (leftLen <= block):
            for i in range(leftLen):
                buf[i] = arr[(lo + i)]
            bi = 0
            ri = (mid + 1)
            wi = lo
            while ((bi < leftLen) and (ri <= hi)):
                compare(wi, ri)
                if (buf[bi] <= arr[ri]):
                    arr[wi] = buf[((bi := bi + 1) - 1)]
                else:
                    arr[wi] = arr[((ri := ri + 1) - 1)]
                write(wi, arr[wi])
                wi += 1
            while (bi < leftLen):
                arr[wi] = buf[((bi := bi + 1) - 1)]
                write(wi, arr[wi])
                wi += 1
            return
        if (rightLen <= block):
            for i in range(rightLen):
                buf[i] = arr[((mid + 1) + i)]
            li = mid
            bi = (rightLen - 1)
            wi = hi
            while ((li >= lo) and (bi >= 0)):
                if (arr[li] > buf[bi]):
                    arr[wi] = arr[((li := li - 1) + 1)]
                else:
                    arr[wi] = buf[((bi := bi - 1) + 1)]
                write(wi, arr[wi])
                wi -= 1
            while (bi >= 0):
                arr[wi] = buf[((bi := bi - 1) + 1)]
                write(wi, arr[wi])
                wi -= 1
            return
        halfLeft = (leftLen // 2)
        splitL = (lo + halfLeft)
        splitR = lowerBound((mid + 1), hi, arr[splitL])
        newMid = (splitL + ((splitR - mid) - 1))
        rotate(splitL, mid, (splitR - 1))
        merge(lo, (splitL - 1), (newMid - 1))
        merge(newMid, (splitR - 1), hi)

    block = (2 if 2 >= int(int((n or 1) ** 0.5)) else int(int((n or 1) ** 0.5)))
    buf = [0] * block
    for i in range(0, n, block):
        insertion(i, (((i + block) - 1) if ((i + block) - 1) <= (n - 1) else (n - 1)))
    width = block
    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):
                merge(lo, mid, hi)
        checkpoint(((width << 1) if (width << 1) <= n else n), n)
        width <<= 1
 #include <vector>
#include <algorithm>
#include <cmath>
void insertion(int lo, int hi);
void reverseRange(int start, int end);
void rotate(int lo, int mid, int hi);
int lowerBound(int lo, int hi, int target);
int upperBound(int lo, int hi, int target);
void merge(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 reverseRange(int start, int end) {
    while((start < end)) {
        std::swap(arr[start], arr[end]);
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverseRange(lo, mid);
    reverseRange((mid + 1), hi);
    reverseRange(lo, hi);
}

int lowerBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int upperBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int leftLen = ((mid - lo) + 1);
    int rightLen = (hi - mid);
    if((leftLen <= block)) {
        for(int i=0; i<leftLen; i++) {
            buf[i] = arr[(lo + i)];
        }
        int bi = 0;
        int ri = (mid + 1);
        int wi = lo;
        while(((bi < leftLen) && (ri <= hi))) {
            compare(wi, ri);
            if((buf[bi] <= arr[ri])) {
                arr[wi] = buf[bi++];
            } else {
                arr[wi] = arr[ri++];
            }
            write(wi, arr[wi]);
            wi++;
        }
        while((bi < leftLen)) {
            arr[wi] = buf[bi++];
            write(wi, arr[wi]);
            wi++;
        }
        return;
    }
    if((rightLen <= block)) {
        for(int i=0; i<rightLen; i++) {
            buf[i] = arr[((mid + 1) + i)];
        }
        int li = mid;
        int bi = (rightLen - 1);
        int wi = hi;
        while(((li >= lo) && (bi >= 0))) {
            if((arr[li] > buf[bi])) {
                arr[wi] = arr[li--];
            } else {
                arr[wi] = buf[bi--];
            }
            write(wi, arr[wi]);
            wi--;
        }
        while((bi >= 0)) {
            arr[wi] = buf[bi--];
            write(wi, arr[wi]);
            wi--;
        }
        return;
    }
    int halfLeft = (leftLen / 2);
    int splitL = (lo + halfLeft);
    int splitR = lowerBound((mid + 1), hi, arr[splitL]);
    int newMid = (splitL + ((splitR - mid) - 1));
    rotate(splitL, mid, (splitR - 1));
    merge(lo, (splitL - 1), (newMid - 1));
    merge(newMid, (splitR - 1), hi);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int block = ((2) > ((int)std::floor((int)std::sqrt(((n) != 0 ? (n) : (1))))) ? (2) : ((int)std::floor((int)std::sqrt(((n) != 0 ? (n) : (1))))));
    std::vector<int> buf(block, 0);
    for(int i=0; i<n; i+=block) {
        insertion(i, ((((i + block) - 1)) < ((n - 1)) ? (((i + block) - 1)) : ((n - 1))));
    }
    for(int width=block; (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);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
} 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 reverseRange(int start, int end) {
    while((start < end)) {
        { int _t = arr[start]; arr[start] = arr[end]; arr[end] = _t; }
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverseRange(lo, mid);
    reverseRange((mid + 1), hi);
    reverseRange(lo, hi);
}

int lowerBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int upperBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int leftLen = ((mid - lo) + 1);
    int rightLen = (hi - mid);
    if((leftLen <= block)) {
        for(int i=0; i<leftLen; i++) {
            buf[i] = arr[(lo + i)];
        }
        int bi = 0;
        int ri = (mid + 1);
        int wi = lo;
        while(((bi < leftLen) && (ri <= hi))) {
            compare(wi, ri);
            if((buf[bi] <= arr[ri])) {
                arr[wi] = buf[bi++];
            } else {
                arr[wi] = arr[ri++];
            }
            write(wi, arr[wi]);
            wi++;
        }
        while((bi < leftLen)) {
            arr[wi] = buf[bi++];
            write(wi, arr[wi]);
            wi++;
        }
        return;
    }
    if((rightLen <= block)) {
        for(int i=0; i<rightLen; i++) {
            buf[i] = arr[((mid + 1) + i)];
        }
        int li = mid;
        int bi = (rightLen - 1);
        int wi = hi;
        while(((li >= lo) && (bi >= 0))) {
            if((arr[li] > buf[bi])) {
                arr[wi] = arr[li--];
            } else {
                arr[wi] = buf[bi--];
            }
            write(wi, arr[wi]);
            wi--;
        }
        while((bi >= 0)) {
            arr[wi] = buf[bi--];
            write(wi, arr[wi]);
            wi--;
        }
        return;
    }
    int halfLeft = (leftLen / 2);
    int splitL = (lo + halfLeft);
    int splitR = lowerBound((mid + 1), hi, arr[splitL]);
    int newMid = (splitL + ((splitR - mid) - 1));
    rotate(splitL, mid, (splitR - 1));
    merge(lo, (splitL - 1), (newMid - 1));
    merge(newMid, (splitR - 1), hi);
}

public void Sort(int[] arr, int n, dynamic stats) {
    int block = Math.Max(2, (int)Math.Floor((double)(int)Math.Sqrt(((n) != 0 ? (n) : (1)))));
    int[] buf = new int[block];
    for(int i=0; i<n; i+=block) {
        insertion(i, Math.Min(((i + block) - 1), (n - 1)));
    }
    for(int width=block; (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)) {
                merge(lo, mid, hi);
            }
        }
        checkpoint(Math.Min((width << 1), n), n);
    }
} #include <stdio.h>
#include <math.h>
#include <stdlib.h>
void insertion(int lo, int hi);
void reverseRange(int start, int end);
void rotate(int lo, int mid, int hi);
int lowerBound(int lo, int hi, int target);
int upperBound(int lo, int hi, int target);
void merge(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 reverseRange(int start, int end) {
    while((start < end)) {
        { int _t = arr[start]; arr[start] = arr[end]; arr[end] = _t; }
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverseRange(lo, mid);
    reverseRange((mid + 1), hi);
    reverseRange(lo, hi);
}

int lowerBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int upperBound(int lo, int hi, int target) {
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) >> 1));
        compare(m, m);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int leftLen = ((mid - lo) + 1);
    int rightLen = (hi - mid);
    if((leftLen <= block)) {
        for(int i=0; i<leftLen; i++) {
            buf[i] = arr[(lo + i)];
        }
        int bi = 0;
        int ri = (mid + 1);
        int wi = lo;
        while(((bi < leftLen) && (ri <= hi))) {
            compare(wi, ri);
            if((buf[bi] <= arr[ri])) {
                arr[wi] = buf[bi++];
            } else {
                arr[wi] = arr[ri++];
            }
            write(wi, arr[wi]);
            wi++;
        }
        while((bi < leftLen)) {
            arr[wi] = buf[bi++];
            write(wi, arr[wi]);
            wi++;
        }
        return;
    }
    if((rightLen <= block)) {
        for(int i=0; i<rightLen; i++) {
            buf[i] = arr[((mid + 1) + i)];
        }
        int li = mid;
        int bi = (rightLen - 1);
        int wi = hi;
        while(((li >= lo) && (bi >= 0))) {
            if((arr[li] > buf[bi])) {
                arr[wi] = arr[li--];
            } else {
                arr[wi] = buf[bi--];
            }
            write(wi, arr[wi]);
            wi--;
        }
        while((bi >= 0)) {
            arr[wi] = buf[bi--];
            write(wi, arr[wi]);
            wi--;
        }
        return;
    }
    int halfLeft = (leftLen / 2);
    int splitL = (lo + halfLeft);
    int splitR = lowerBound((mid + 1), hi, arr[splitL]);
    int newMid = (splitL + ((splitR - mid) - 1));
    rotate(splitL, mid, (splitR - 1));
    merge(lo, (splitL - 1), (newMid - 1));
    merge(newMid, (splitR - 1), hi);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int block = ((2) > ((int)floor((int)sqrt(((n) != 0 ? (n) : (1))))) ? (2) : ((int)floor((int)sqrt(((n) != 0 ? (n) : (1))))));
    int* buf = (int*)malloc((block) * sizeof(int));
    for(int i=0; i<n; i+=block) {
        insertion(i, ((((i + block) - 1)) < ((n - 1)) ? (((i + block) - 1)) : ((n - 1))));
    }
    for(int width=block; (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);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
} 