Sample Sort — VisualAlgorithms Docs

How it works

Generalizes quicksort to many pivots: it draws a set of splitter samples, distributes each range into buckets between consecutive splitters, writes the buckets straight back, and recurses. Each level visibly regroups the bars into ordered buckets.
Implementation

      
 function sampleSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const INSERTION_THRESHOLD = 32;
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.insertionThreshold = INSERTION_THRESHOLD;
  function insertionSort(lo, hi) {
    recordMetric('insertionSortCalls');
    for (let i = lo + 1; i < hi; i++) {
      const value = arr[i];
      let j = i;
      while (j > lo) {
        compare(j - 1, i);
        if (arr[j - 1] <= value) break;
        arr[j] = arr[j - 1];
        write(j, arr[j]);
        j--;
      }
      arr[j] = value;
      write(j, value);
    }
    for (let i = lo; i < hi; i++) markSorted(i);
  }
  function sort(lo, hi) {
    const len = hi - lo;
    if (len <= INSERTION_THRESHOLD) {
      insertionSort(lo, hi);
      return;
    }
    const mid = lo + (len >> 1);
    const bucketCount = Math.max(2, Math.floor(Math.sqrt(len)));
    const step = Math.floor(len / bucketCount);
    const splitters = [];
    for (let s = 1; s < bucketCount; s++) splitters.push(arr[lo + s * step]);
    splitters.sort((a, b) => a - b);
    const splitterCount = splitters.length;
    recordMetric('splitterSelections', splitterCount);
    const buckets = [];
    for (let b = 0; b <= splitterCount; b++) buckets.push([]);
    for (let i = lo; i < hi; i++) {
      compare(i, mid);
      const value = arr[i];
      let blo = 0;
      let bhi = splitterCount;
      while (blo < bhi) {
        const bm = blo + bhi >> 1;
        if (splitters[bm] <= value) blo = bm + 1; else bhi = bm;
      }
      buckets[blo].push(value);
    }
    let maxBucket = 0;
    for (let b = 0; b < buckets.length; b++) {
      if (buckets[b].length > maxBucket) maxBucket = buckets[b].length;
    }
    if (maxBucket === len) {
      insertionSort(lo, hi);
      return;
    }
    recordMetric('distributionPasses');
    let w = lo;
    for (let b = 0; b < buckets.length; b++) {
      const bucket = buckets[b];
      const start = w;
      for (let i = 0; i < bucket.length; i++) {
        arr[w] = bucket[i];
        write(w, bucket[i]);
        w++;
      }
      checkpoint(start, n);
      sort(start, w);
    }
  }
  sort(0, n);
  checkpoint(n, n);
}
 def sampleSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def insertionSort(lo, hi):
        recordMetric("insertionSortCalls")
        for i in range((lo + 1), hi):
            value = arr[i]
            j = i
            while (j > lo):
                compare((j - 1), i)
                if (arr[(j - 1)] <= value):
                    break
                arr[j] = arr[(j - 1)]
                write(j, arr[j])
                j -= 1
            arr[j] = value
            write(j, value)
        for i in range(lo, hi):
            markSorted(i)

    def sort(lo, hi):
        len = (hi - lo)
        if (len <= INSERTION_THRESHOLD):
            insertionSort(lo, hi)
            return
        mid = (lo + (len >> 1))
        bucketCount = (2 if 2 >= int(int(len ** 0.5)) else int(int(len ** 0.5)))
        step = int(len / bucketCount)
        splitters = []
        for s in range(1, bucketCount):
            splitters.append(arr[(lo + (s * step))])
        splitters.sort()
        splitterCount = len(splitters)
        recordMetric("splitterSelections", splitterCount)
        buckets = []
        for b in range((splitterCount + 1)):
            buckets.append([])
        for i in range(lo, hi):
            compare(i, mid)
            value = arr[i]
            blo = 0
            bhi = splitterCount
            while (blo < bhi):
                bm = ((blo + bhi) >> 1)
                if (splitters[bm] <= value):
                    blo = (bm + 1)
                else:
                    bhi = bm
            buckets[blo].append(value)
        maxBucket = 0
        for b in range(len(buckets)):
            if (len(buckets[b]) > maxBucket):
                maxBucket = len(buckets[b])
        if (maxBucket == len):
            insertionSort(lo, hi)
            return
        recordMetric("distributionPasses")
        w = lo
        for b in range(len(buckets)):
            bucket = buckets[b]
            start = w
            for i in range(len(bucket)):
                arr[w] = bucket[i]
                write(w, bucket[i])
                w += 1
            checkpoint(start, n)
            sort(start, w)

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    INSERTION_THRESHOLD = 32
    metrics.insertionThreshold = INSERTION_THRESHOLD
    sort(0, n)
    checkpoint(n, n)
 #include <vector>
#include <algorithm>
#include <cmath>
void recordMetric(int name, int );
void insertionSort(int lo, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int bucketCount = ((2) > ((int)std::floor((int)std::sqrt(len))) ? (2) : ((int)std::floor((int)std::sqrt(len))));
    int step = (len / bucketCount);
    std::vector<int> splitters;
    for(int s=1; s<bucketCount; s++) {
        splitters.push_back(arr[(lo + (s * step))]);
    }
    std::sort(splitters.begin(), splitters.end());
    int splitterCount = (int)splitters.size();
    recordMetric("splitterSelections", splitterCount);
    std::vector<int> buckets;
    for(int b=0; b<(splitterCount + 1); b++) {
        buckets.push_back({});
    }
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        int blo = 0;
        int bhi = splitterCount;
        while((blo < bhi)) {
            int bm = ((blo + bhi) >> 1);
            if((splitters[bm] <= value)) {
                blo = (bm + 1);
            } else {
                bhi = bm;
            }
        }
        buckets[blo].push_back(value);
    }
    int maxBucket = 0;
    for(int b=0; b<(int)buckets.size(); b++) {
        if((n > maxBucket)) {
            maxBucket = n;
        }
    }
    if((maxBucket == len)) {
        insertionSort(lo, hi);
        return;
    }
    recordMetric("distributionPasses");
    int w = lo;
    for(int b=0; b<(int)buckets.size(); b++) {
        int bucket = buckets[b];
        int start = w;
        for(int i=0; i<n; i++) {
            arr[w] = bucket[i];
            write(w, bucket[i]);
            w++;
        }
        checkpoint(start, n);
        sort(start, w);
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 32;
    int metrics = educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int bucketCount = Math.Max(2, (int)Math.Floor((double)(int)Math.Sqrt(len)));
    int step = (len / bucketCount);
    var splitters = new List<int>();
    for(int s=1; s<bucketCount; s++) {
        splitters.Add(arr[(lo + (s * step))]);
    }
    Array.Sort(splitters);
    int splitterCount = splitters.Count;
    recordMetric("splitterSelections", splitterCount);
    var buckets = new List<int>();
    for(int b=0; b<(splitterCount + 1); b++) {
        buckets.Add(new int[] {});
    }
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        int blo = 0;
        int bhi = splitterCount;
        while((blo < bhi)) {
            int bm = ((blo + bhi) >> 1);
            if((splitters[bm] <= value)) {
                blo = (bm + 1);
            } else {
                bhi = bm;
            }
        }
        buckets[blo][buckets[blo]_len++] = value;
    }
    int maxBucket = 0;
    for(int b=0; b<buckets.Count; b++) {
        if((n > maxBucket)) {
            maxBucket = n;
        }
    }
    if((maxBucket == len)) {
        insertionSort(lo, hi);
        return;
    }
    recordMetric("distributionPasses");
    int w = lo;
    for(int b=0; b<buckets.Count; b++) {
        int bucket = buckets[b];
        int start = w;
        for(int i=0; i<n; i++) {
            arr[w] = bucket[i];
            write(w, bucket[i]);
            w++;
        }
        checkpoint(start, n);
        sort(start, w);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 32;
    int metrics = stats.educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} #include <stdio.h>
#include <math.h>
#include <stdlib.h>
void recordMetric(int name, int );
void insertionSort(int lo, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int bucketCount = ((2) > ((int)floor((int)sqrt(len))) ? (2) : ((int)floor((int)sqrt(len))));
    int step = (len / bucketCount);
    int* splitters = (int*)malloc(n * sizeof(int)); int splitters_len = 0;
    for(int s=1; s<bucketCount; s++) {
        splitters[splitters_len++] = arr[(lo + (s * step))];
    }
    splitters_sort(0);
    int splitterCount = splitters_len;
    recordMetric("splitterSelections", splitterCount);
    int* buckets = (int*)malloc(n * sizeof(int)); int buckets_len = 0;
    for(int b=0; b<(splitterCount + 1); b++) {
        buckets[buckets_len++] = {};
    }
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        int blo = 0;
        int bhi = splitterCount;
        while((blo < bhi)) {
            int bm = ((blo + bhi) >> 1);
            if((splitters[bm] <= value)) {
                blo = (bm + 1);
            } else {
                bhi = bm;
            }
        }
        buckets[blo][buckets[blo]_len++] = value;
    }
    int maxBucket = 0;
    for(int b=0; b<buckets_len; b++) {
        if((n > maxBucket)) {
            maxBucket = n;
        }
    }
    if((maxBucket == len)) {
        insertionSort(lo, hi);
        return;
    }
    recordMetric("distributionPasses");
    int w = lo;
    for(int b=0; b<buckets_len; b++) {
        int bucket = buckets[b];
        int start = w;
        for(int i=0; i<n; i++) {
            arr[w] = bucket[i];
            write(w, bucket[i]);
            w++;
        }
        checkpoint(start, n);
        sort(start, w);
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 32;
    int metrics = (*educational).metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} 