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, stats) {
  const n = arr.length;
  function swap(i, j) {
    let t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    swap(i, j);
  }
  function rotate(start, mid, end) {
    if (start === mid || mid === end) return;
    let next = mid;
    while (start !== next) {
      swap(start++, next++);
      if (next === end) next = mid; else if (start === mid) mid = next;
    }
  }
  function mergeInPlace(start, mid, end) {
    if (start >= mid || mid >= end) return;
    if (arr[mid - 1] <= arr[mid]) return;
    let left = start, right = mid;
    while (left < mid && right < end) {
      compare(left, right);
      if (arr[left] <= arr[right]) {
        left++;
      } else {
        let tempRight = right;
        while (tempRight < end) {
          if (arr[tempRight] >= arr[left]) break;
          tempRight++;
        }
        rotate(left, right, tempRight);
        left += tempRight - right;
        mid += tempRight - right;
        right = tempRight;
      }
    }
  }
  function sort(l, r) {
    if (r - l < 1) return;
    if (r - l === 1) {
      if (arr[l] > arr[r]) swap(l, r);
      return;
    }
    const m = l + Math.floor((r - l) / 2);
    sort(l, m);
    sort(m + 1, r);
    mergeInPlace(l, m + 1, r + 1);
  }
  sort(0, n - 1);
  for (let i = 0; i < n; i++) markSorted(i);
}
 def blockSort(arr, stats):
    def swap(i, j):
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
        swap(i, j)

    def rotate(start, mid, end):
        if ((start == mid) or (mid == end)):
            return
        next = mid
        while (start != next):
            swap(((start := start + 1) - 1), ((next := next + 1) - 1))
            if (next == end):
                next = mid
            elif (start == mid):
                mid = next

    def mergeInPlace(start, mid, end):
        if ((start >= mid) or (mid >= end)):
            return
        if (arr[(mid - 1)] <= arr[mid]):
            return
        left = start
        right = mid
        while ((left < mid) and (right < end)):
            compare(left, right)
            if (arr[left] <= arr[right]):
                left += 1
            else:
                tempRight = right
                while (tempRight < end):
                    if (arr[tempRight] >= arr[left]):
                        break
                    tempRight += 1
                rotate(left, right, tempRight)
                left += (tempRight - right)
                mid += (tempRight - right)
                right = tempRight

    def sort(l, r):
        if ((r - l) < 1):
            return
        if ((r - l) == 1):
            if (arr[l] > arr[r]):
                swap(l, r)
            return
        m = (l + ((r - l) // 2))
        sort(l, m)
        sort((m + 1), r)
        mergeInPlace(l, (m + 1), (r + 1))

    sort(0, (n - 1))
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void swap(int i, int j);
void rotate(int start, int mid, int end);
void mergeInPlace(int start, int mid, int end);
void sort(int l, int r);

void swap(int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    swap(i, j);
}

void rotate(int start, int mid, int end) {
    if(((start == mid) || (mid == end))) {
        return;
    }
    int next = mid;
    while((start != next)) {
        swap(start++, next++);
        if((next == end)) {
            next = mid;
        } else if((start == mid)) {
            mid = next;
        }
    }
}

void mergeInPlace(int start, int mid, int end) {
    if(((start >= mid) || (mid >= end))) {
        return;
    }
    if((arr[(mid - 1)] <= arr[mid])) {
        return;
    }
    int left = start;
    int right = mid;
    while(((left < mid) && (right < end))) {
        compare(left, right);
        if((arr[left] <= arr[right])) {
            left++;
        } else {
            int tempRight = right;
            while((tempRight < end)) {
                if((arr[tempRight] >= arr[left])) {
                    break;
                }
                tempRight++;
            }
            rotate(left, right, tempRight);
            left += (tempRight - right);
            mid += (tempRight - right);
            right = tempRight;
        }
    }
}

void sort(int l, int r) {
    if(((r - l) < 1)) {
        return;
    }
    if(((r - l) == 1)) {
        if((arr[l] > arr[r])) {
            swap(l, r);
        }
        return;
    }
    int m = (l + ((r - l) / 2));
    sort(l, m);
    sort((m + 1), r);
    mergeInPlace(l, (m + 1), (r + 1));
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} void swap(int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    swap(i, j);
}

void rotate(int start, int mid, int end) {
    if(((start == mid) || (mid == end))) {
        return;
    }
    int next = mid;
    while((start != next)) {
        swap(start++, next++);
        if((next == end)) {
            next = mid;
        } else if((start == mid)) {
            mid = next;
        }
    }
}

void mergeInPlace(int start, int mid, int end) {
    if(((start >= mid) || (mid >= end))) {
        return;
    }
    if((arr[(mid - 1)] <= arr[mid])) {
        return;
    }
    int left = start;
    int right = mid;
    while(((left < mid) && (right < end))) {
        compare(left, right);
        if((arr[left] <= arr[right])) {
            left++;
        } else {
            int tempRight = right;
            while((tempRight < end)) {
                if((arr[tempRight] >= arr[left])) {
                    break;
                }
                tempRight++;
            }
            rotate(left, right, tempRight);
            left += (tempRight - right);
            mid += (tempRight - right);
            right = tempRight;
        }
    }
}

void sort(int l, int r) {
    if(((r - l) < 1)) {
        return;
    }
    if(((r - l) == 1)) {
        if((arr[l] > arr[r])) {
            swap(l, r);
        }
        return;
    }
    int m = (l + ((r - l) / 2));
    sort(l, m);
    sort((m + 1), r);
    mergeInPlace(l, (m + 1), (r + 1));
}

public void Sort(int[] arr, int n, dynamic stats) {
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void swap(int i, int j);
void rotate(int start, int mid, int end);
void mergeInPlace(int start, int mid, int end);
void sort(int l, int r);

void swap(int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    swap(i, j);
}

void rotate(int start, int mid, int end) {
    if(((start == mid) || (mid == end))) {
        return;
    }
    int next = mid;
    while((start != next)) {
        swap(start++, next++);
        if((next == end)) {
            next = mid;
        } else if((start == mid)) {
            mid = next;
        }
    }
}

void mergeInPlace(int start, int mid, int end) {
    if(((start >= mid) || (mid >= end))) {
        return;
    }
    if((arr[(mid - 1)] <= arr[mid])) {
        return;
    }
    int left = start;
    int right = mid;
    while(((left < mid) && (right < end))) {
        compare(left, right);
        if((arr[left] <= arr[right])) {
            left++;
        } else {
            int tempRight = right;
            while((tempRight < end)) {
                if((arr[tempRight] >= arr[left])) {
                    break;
                }
                tempRight++;
            }
            rotate(left, right, tempRight);
            left += (tempRight - right);
            mid += (tempRight - right);
            right = tempRight;
        }
    }
}

void sort(int l, int r) {
    if(((r - l) < 1)) {
        return;
    }
    if(((r - l) == 1)) {
        if((arr[l] > arr[r])) {
            swap(l, r);
        }
        return;
    }
    int m = (l + ((r - l) / 2));
    sort(l, m);
    sort((m + 1), r);
    mergeInPlace(l, (m + 1), (r + 1));
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 