IntroSort

function introSort(arr, stats) {
  const n = arr.length;
  const sorted = new Set();
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const maxDepth = Math.floor(2 * Math.log2(n));
  function swap(i, j) {
    if (i === j) return;
    swap(i, j, {
      sorted
    });
    const t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
  function insertSort(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, {
          sorted
        });
        if (arr[j] <= key) break;
        arr[j + 1] = arr[j];
        write(j + 1, arr[j + 1], {
          sorted
        });
        j--;
      }
      arr[j + 1] = key;
      write(j + 1, key, {
        sorted
      });
    }
  }
  function siftDown(lo, root, end) {
    let parent = root;
    while (2 * (parent - lo) + 1 + lo <= end) {
      let child = 2 * (parent - lo) + 1 + lo;
      if (child + 1 <= end) {
        compare(child, child + 1, {
          sorted
        });
        if (arr[child] < arr[child + 1]) {
          child++;
        }
      }
      compare(parent, child, {
        sorted
      });
      if (arr[parent] < arr[child]) {
        swap(parent, child);
        parent = child;
      } else break;
    }
  }
  function heapRange(lo, hi) {
    const size = hi - lo + 1;
    for (let i = lo + Math.floor(size / 2) - 1; i >= lo; i--) siftDown(lo, i, hi);
    for (let i = hi; i > lo; i--) {
      swap(lo, i);
      markSorted(i);
      siftDown(lo, lo, i - 1);
    }
    markSorted(lo);
  }
  function median3(lo, mid, hi) {
    compare(mid, lo, {
      sorted
    });
    if (arr[mid] < arr[lo]) swap(lo, mid);
    compare(hi, lo, {
      sorted
    });
    if (arr[hi] < arr[lo]) swap(lo, hi);
    compare(hi, mid, {
      sorted
    });
    if (arr[hi] < arr[mid]) swap(mid, hi);
  }
  function introRec(lo, hi, depth) {
    if (hi - lo < 16) {
      insertSort(lo, hi);
      return;
    }
    if (depth === 0) {
      heapRange(lo, hi);
      return;
    }
    const mid = lo + Math.floor((hi - lo) / 2);
    median3(lo, mid, hi);
    const pivot = arr[mid];
    swap(mid, hi - 1);
    let i = lo, j = hi - 1;
    while (true) {
      do {
        i++;
        compare(i, hi - 1, {
          sorted
        });
      } while (arr[i] < pivot);
      do {
        j--;
        compare(j, hi - 1, {
          sorted
        });
      } while (arr[j] > pivot);
      if (i >= j) break;
      swap(i, j);
    }
    swap(i, hi - 1);
    markSorted(i);
    introRec(lo, i - 1, depth - 1);
    introRec(i + 1, hi, depth - 1);
    checkpoint(sorted.size, n);
  }
  introRec(0, n - 1, maxDepth);
  for (let i = 0; i < n; i++) markSorted(i);
}

from types import SimpleNamespace

def introSort(arr, stats):
    def swap(i, j):
        if (i == j):
            return
        swap(i, j, SimpleNamespace(sorted=sorted))
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t

    def insertSort(lo, hi):
        for i in range((lo + 1), (hi + 1)):
            key = arr[i]
            j = (i - 1)
            while (j >= lo):
                compare(j, (j + 1), SimpleNamespace(sorted=sorted))
                if (arr[j] <= key):
                    break
                arr[(j + 1)] = arr[j]
                write((j + 1), arr[(j + 1)], SimpleNamespace(sorted=sorted))
                j -= 1
            arr[(j + 1)] = key
            write((j + 1), key, SimpleNamespace(sorted=sorted))

    def siftDown(lo, root, end):
        parent = root
        while ((((2 * (parent - lo)) + 1) + lo) <= end):
            child = (((2 * (parent - lo)) + 1) + lo)
            if ((child + 1) <= end):
                compare(child, (child + 1), SimpleNamespace(sorted=sorted))
                if (arr[child] < arr[(child + 1)]):
                    child += 1
            compare(parent, child, SimpleNamespace(sorted=sorted))
            if (arr[parent] < arr[child]):
                swap(parent, child)
                parent = child
            else:
                break

    def heapRange(lo, hi):
        size = ((hi - lo) + 1)
        for i in range(((lo + (size // 2)) - 1), (lo - 1), -1):
            siftDown(lo, i, hi)
        for i in range(hi, lo, -1):
            swap(lo, i)
            markSorted(i)
            siftDown(lo, lo, (i - 1))
        markSorted(lo)

    def median3(lo, mid, hi):
        compare(mid, lo, SimpleNamespace(sorted=sorted))
        if (arr[mid] < arr[lo]):
            swap(lo, mid)
        compare(hi, lo, SimpleNamespace(sorted=sorted))
        if (arr[hi] < arr[lo]):
            swap(lo, hi)
        compare(hi, mid, SimpleNamespace(sorted=sorted))
        if (arr[hi] < arr[mid]):
            swap(mid, hi)

    def introRec(lo, hi, depth):
        if ((hi - lo) < 16):
            insertSort(lo, hi)
            return
        if (depth == 0):
            heapRange(lo, hi)
            return
        mid = (lo + ((hi - lo) // 2))
        median3(lo, mid, hi)
        pivot = arr[mid]
        swap(mid, (hi - 1))
        i = lo
        j = (hi - 1)
        while True:
            while True:
                i += 1
                compare(i, (hi - 1), SimpleNamespace(sorted=sorted))
                if not ((arr[i] < pivot)):
                    break
            while True:
                j -= 1
                compare(j, (hi - 1), SimpleNamespace(sorted=sorted))
                if not ((arr[j] > pivot)):
                    break
            if (i >= j):
                break
            swap(i, j)
        swap(i, (hi - 1))
        markSorted(i)
        introRec(lo, (i - 1), (depth - 1))
        introRec((i + 1), hi, (depth - 1))
        checkpoint(sorted.size, n)

    sorted = set()
    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    maxDepth = int((2 * (__import__("math").log2(n) if (n) > 0 else 0)))
    introRec(0, (n - 1), maxDepth)
    for i in range(n):
        markSorted(i)

#include <vector>
#include <algorithm>
#include <cmath>
void swap(int i, int j);
void insertSort(int lo, int hi);
void siftDown(int lo, int root, int end);
void heapRange(int lo, int hi);
void median3(int lo, int mid, int hi);
void introRec(int lo, int hi, int depth);

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

void insertSort(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), {sorted: sorted});
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)], {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key, {sorted: sorted});
    }
}

void siftDown(int lo, int root, int end) {
    int parent = root;
    while(((((2 * (parent - lo)) + 1) + lo) <= end)) {
        int child = (((2 * (parent - lo)) + 1) + lo);
        if(((child + 1) <= end)) {
            compare(child, (child + 1), {sorted: sorted});
            if((arr[child] < arr[(child + 1)])) {
                child++;
            }
        }
        compare(parent, child, {sorted: sorted});
        if((arr[parent] < arr[child])) {
            swap(parent, child);
            parent = child;
        } else {
            break;
        }
    }
}

void heapRange(int lo, int hi) {
    int size = ((hi - lo) + 1);
    for(int i=((lo + (size / 2)) - 1); i>(lo - 1); i--) {
        siftDown(lo, i, hi);
    }
    for(int i=hi; i>lo; i--) {
        swap(lo, i);
        markSorted(i);
        siftDown(lo, lo, (i - 1));
    }
    markSorted(lo);
}

void median3(int lo, int mid, int hi) {
    compare(mid, lo, {sorted: sorted});
    if((arr[mid] < arr[lo])) {
        swap(lo, mid);
    }
    compare(hi, lo, {sorted: sorted});
    if((arr[hi] < arr[lo])) {
        swap(lo, hi);
    }
    compare(hi, mid, {sorted: sorted});
    if((arr[hi] < arr[mid])) {
        swap(mid, hi);
    }
}

void introRec(int lo, int hi, int depth) {
    if(((hi - lo) < 16)) {
        insertSort(lo, hi);
        return;
    }
    if((depth == 0)) {
        heapRange(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) / 2));
    median3(lo, mid, hi);
    int pivot = arr[mid];
    swap(mid, (hi - 1));
    int i = lo;
    int j = (hi - 1);
    while(1) {
        do {
            i++;
            compare(i, (hi - 1), {sorted: sorted});
        } while((arr[i] < pivot));
        do {
            j--;
            compare(j, (hi - 1), {sorted: sorted});
        } while((arr[j] > pivot));
        if((i >= j)) {
            break;
        }
        swap(i, j);
    }
    swap(i, (hi - 1));
    markSorted(i);
    introRec(lo, (i - 1), (depth - 1));
    introRec((i + 1), hi, (depth - 1));
    checkpoint(sorted.size, n);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int sorted = 0;
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int maxDepth = (int)std::floor((2 * (int)std::log2(n)));
    introRec(0, (n - 1), maxDepth);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

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

void insertSort(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), {sorted: sorted});
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)], {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key, {sorted: sorted});
    }
}

void siftDown(int lo, int root, int end) {
    int parent = root;
    while(((((2 * (parent - lo)) + 1) + lo) <= end)) {
        int child = (((2 * (parent - lo)) + 1) + lo);
        if(((child + 1) <= end)) {
            compare(child, (child + 1), {sorted: sorted});
            if((arr[child] < arr[(child + 1)])) {
                child++;
            }
        }
        compare(parent, child, {sorted: sorted});
        if((arr[parent] < arr[child])) {
            swap(parent, child);
            parent = child;
        } else {
            break;
        }
    }
}

void heapRange(int lo, int hi) {
    int size = ((hi - lo) + 1);
    for(int i=((lo + (size / 2)) - 1); i>(lo - 1); i--) {
        siftDown(lo, i, hi);
    }
    for(int i=hi; i>lo; i--) {
        swap(lo, i);
        markSorted(i);
        siftDown(lo, lo, (i - 1));
    }
    markSorted(lo);
}

void median3(int lo, int mid, int hi) {
    compare(mid, lo, {sorted: sorted});
    if((arr[mid] < arr[lo])) {
        swap(lo, mid);
    }
    compare(hi, lo, {sorted: sorted});
    if((arr[hi] < arr[lo])) {
        swap(lo, hi);
    }
    compare(hi, mid, {sorted: sorted});
    if((arr[hi] < arr[mid])) {
        swap(mid, hi);
    }
}

void introRec(int lo, int hi, int depth) {
    if(((hi - lo) < 16)) {
        insertSort(lo, hi);
        return;
    }
    if((depth == 0)) {
        heapRange(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) / 2));
    median3(lo, mid, hi);
    int pivot = arr[mid];
    swap(mid, (hi - 1));
    int i = lo;
    int j = (hi - 1);
    while(true) {
        do {
            i++;
            compare(i, (hi - 1), {sorted: sorted});
        } while((arr[i] < pivot));
        do {
            j--;
            compare(j, (hi - 1), {sorted: sorted});
        } while((arr[j] > pivot));
        if((i >= j)) {
            break;
        }
        swap(i, j);
    }
    swap(i, (hi - 1));
    markSorted(i);
    introRec(lo, (i - 1), (depth - 1));
    introRec((i + 1), hi, (depth - 1));
    checkpoint(sorted.size, n);
}

public void Sort(int[] arr, int n, dynamic stats) {
    int sorted = 0;
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int maxDepth = (int)Math.Floor((double)(2 * (int)Math.Log((double)n, 2)));
    introRec(0, (n - 1), maxDepth);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

#include <stdio.h>
#include <math.h>
void swap(int i, int j);
void insertSort(int lo, int hi);
void siftDown(int lo, int root, int end);
void heapRange(int lo, int hi);
void median3(int lo, int mid, int hi);
void introRec(int lo, int hi, int depth);

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

void insertSort(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), {sorted: sorted});
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)], {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key, {sorted: sorted});
    }
}

void siftDown(int lo, int root, int end) {
    int parent = root;
    while(((((2 * (parent - lo)) + 1) + lo) <= end)) {
        int child = (((2 * (parent - lo)) + 1) + lo);
        if(((child + 1) <= end)) {
            compare(child, (child + 1), {sorted: sorted});
            if((arr[child] < arr[(child + 1)])) {
                child++;
            }
        }
        compare(parent, child, {sorted: sorted});
        if((arr[parent] < arr[child])) {
            swap(parent, child);
            parent = child;
        } else {
            break;
        }
    }
}

void heapRange(int lo, int hi) {
    int size = ((hi - lo) + 1);
    for(int i=((lo + (size / 2)) - 1); i>(lo - 1); i--) {
        siftDown(lo, i, hi);
    }
    for(int i=hi; i>lo; i--) {
        swap(lo, i);
        markSorted(i);
        siftDown(lo, lo, (i - 1));
    }
    markSorted(lo);
}

void median3(int lo, int mid, int hi) {
    compare(mid, lo, {sorted: sorted});
    if((arr[mid] < arr[lo])) {
        swap(lo, mid);
    }
    compare(hi, lo, {sorted: sorted});
    if((arr[hi] < arr[lo])) {
        swap(lo, hi);
    }
    compare(hi, mid, {sorted: sorted});
    if((arr[hi] < arr[mid])) {
        swap(mid, hi);
    }
}

void introRec(int lo, int hi, int depth) {
    if(((hi - lo) < 16)) {
        insertSort(lo, hi);
        return;
    }
    if((depth == 0)) {
        heapRange(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) / 2));
    median3(lo, mid, hi);
    int pivot = arr[mid];
    swap(mid, (hi - 1));
    int i = lo;
    int j = (hi - 1);
    while(1) {
        do {
            i++;
            compare(i, (hi - 1), {sorted: sorted});
        } while((arr[i] < pivot));
        do {
            j--;
            compare(j, (hi - 1), {sorted: sorted});
        } while((arr[j] > pivot));
        if((i >= j)) {
            break;
        }
        swap(i, j);
    }
    swap(i, (hi - 1));
    markSorted(i);
    introRec(lo, (i - 1), (depth - 1));
    introRec((i + 1), hi, (depth - 1));
    checkpoint(sorted.size, n);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int sorted = 0;
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int maxDepth = (int)floor((2 * (int)log2(n)));
    introRec(0, (n - 1), maxDepth);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}