Block Sort — VisualAlgorithms Docs

How it works

Stable in-place merge sort: recursively sorts the two halves, then merges them without an auxiliary array by rotating out-of-order runs into position (a block-rotation merge).

Implementation

      
 function blockSort(arr) {
  const n = arr.length;
  const blockSize = Math.max(1, Math.floor(Math.sqrt(n)));
  // Sort each block with insertion sort
  for (let i = 0; i < n; i += blockSize) {
    const end = Math.min(i + blockSize, n);
    for (let j = i + 1; j < end; j++) {
      let key = arr[j], k = j - 1;
      while (k >= i && arr[k] > key) arr[k+1] = arr[k], k--;
      arr[k+1] = key;
    }
  }
  // Merge blocks in-place
  mergeBlocks(arr, blockSize);
} def block_sort(arr):
    n = len(arr)
    block = max(1, int(n ** 0.5))
    for i in range(0, n, block):
        end = min(i + block, n)
        for j in range(i + 1, end):
            key, k = arr[j], j - 1
            while k >= i and arr[k] > key:
                arr[k+1] = arr[k]; k -= 1
            arr[k+1] = key
    merge_blocks(arr, block) void blockSort(vector<int>& arr) {
  int n = arr.size();
  int block = max(1, (int)sqrt(n));
  for (int i = 0; i < n; i += block) {
    int end = min(i + block, n);
    for (int j = i + 1; j < end; j++) {
      int key = arr[j], k = j - 1;
      while (k >= i && arr[k] > key) arr[k+1] = arr[k--];
      arr[k+1] = key;
    }
  }
  mergeBlocks(arr, block);
} void BlockSort(int[] arr) {
  int n = arr.Length;
  int block = Math.Max(1, (int)Math.Sqrt(n));
  for (int i = 0; i < n; i += block) {
    int end = Math.Min(i + block, n);
    for (int j = i + 1; j < end; j++) {
      int key = arr[j], k = j - 1;
      while (k >= i && arr[k] > key) arr[k+1] = arr[k--];
      arr[k+1] = key;
    }
  }
  MergeBlocks(arr, block);
} void blockSort(int arr[], int n) {
  int block = (int)sqrt(n);
  if (block < 1) block = 1;
  for (int i = 0; i < n; i += block) {
    int end = i + block < n ? i + block : n;
    for (int j = i + 1; j < end; j++) {
      int key = arr[j], k = j - 1;
      while (k >= i && arr[k] > key)
        { arr[k+1] = arr[k]; k--; }
      arr[k+1] = key;
    }
  }
  mergeBlocks(arr, n, block);
} 