Library Sort

function librarySort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  let sparseSize = 1;
  while (sparseSize < n * 2) sparseSize <<= 1;
  let sparse = new Array(sparseSize).fill(undefined);
  const ordered = [];
  const valueAt = pos => {
    return sparse[ordered[pos]];
  };
  const lowerBound = v => {
    let lo = 0, hi = ordered.length;
    while (lo < hi) {
      const mid = lo + hi >> 1;
      if (valueAt(mid) < v) lo = mid + 1; else hi = mid;
    }
    return lo;
  };
  const rebalance = () => {
    const values = ordered.map(idx => sparse[idx]);
    sparseSize <<= 1;
    sparse = new Array(sparseSize).fill(undefined);
    ordered.length = 0;
    const gap = Math.max(2, Math.floor(sparseSize / Math.max(1, values.length + 1)));
    let cursor = gap;
    for (let i = 0; i < values.length; i++) {
      const v = values[i];
      if (cursor >= sparseSize) cursor = sparseSize - 1;
      sparse[cursor] = v;
      ordered.push(cursor);
      cursor += gap;
    }
  };
  const insertValue = v => {
    while (true) {
      if (ordered.length === 0) {
        const mid = Math.floor(sparseSize / 2);
        sparse[mid] = v;
        ordered.push(mid);
        return;
      }
      const pos = lowerBound(v);
      const left = pos > 0 ? ordered[pos - 1] : -1;
      const right = pos < ordered.length ? ordered[pos] : sparseSize;
      const target = Math.floor((left + right) / 2);
      let gapIdx = -1;
      for (let d = 0; d < sparseSize; d++) {
        const a = target - d;
        const b = target + d;
        if (a >= 0 && sparse[a] === undefined) {
          gapIdx = a;
          break;
        }
        if (b < sparseSize && sparse[b] === undefined) {
          gapIdx = b;
          break;
        }
      }
      if (gapIdx === -1) {
        rebalance();
        continue;
      }
      if (gapIdx < target) {
        for (let i = gapIdx; i < target; i++) {
          sparse[i] = sparse[i + 1];
        }
        for (let i = 0; i < ordered.length; i++) {
          if (ordered[i] > gapIdx && ordered[i] <= target) ordered[i]--;
        }
      } else if (gapIdx > target) {
        for (let i = gapIdx; i > target; i--) {
          sparse[i] = sparse[i - 1];
        }
        for (let i = 0; i < ordered.length; i++) {
          if (ordered[i] >= target && ordered[i] < gapIdx) ordered[i]++;
        }
      }
      sparse[target] = v;
      ordered.splice(pos, 0, target);
      return;
    }
  };
  for (let i = 0; i < n; i++) {
    insertValue(arr[i]);
    compare(i, i);
  }
  for (let i = 0; i < n; i++) {
    arr[i] = sparse[ordered[i]];
    write(i, arr[i]);
    markSorted(i);
  }
}

def librarySort(arr, stats):
    def valueAt(pos):
        return sparse[ordered[pos]]

    def lowerBound(v):
        lo = 0
        hi = len(ordered)
        while (lo < hi):
            mid = ((lo + hi) >> 1)
            if (valueAt(mid) < v):
                lo = (mid + 1)
            else:
                hi = mid
        return lo

    def rebalance():
        nonlocal sparseSize, sparse
        values = [sparse[idx] for idx in ordered]
        sparseSize <<= 1
        sparse = [None] * sparseSize
        ordered.clear()
        gap = (2 if 2 >= int(sparseSize / (1 if 1 >= (len(values) + 1) else (len(values) + 1))) else int(sparseSize / (1 if 1 >= (len(values) + 1) else (len(values) + 1))))
        cursor = gap
        for i in range(len(values)):
            v = values[i]
            if (cursor >= sparseSize):
                cursor = (sparseSize - 1)
            sparse[cursor] = v
            ordered.append(cursor)
            cursor += gap

    def insertValue(v):
        while True:
            if (len(ordered) == 0):
                mid = (sparseSize // 2)
                sparse[mid] = v
                ordered.append(mid)
                return
            pos = lowerBound(v)
            left = (ordered[(pos - 1)] if (pos > 0) else -1)
            right = (ordered[pos] if (pos < len(ordered)) else sparseSize)
            target = ((left + right) // 2)
            gapIdx = -1
            for d in range(sparseSize):
                a = (target - d)
                b = (target + d)
                if ((a >= 0) and (sparse[a] == None)):
                    gapIdx = a
                    break
                if ((b < sparseSize) and (sparse[b] == None)):
                    gapIdx = b
                    break
            if (gapIdx == -1):
                rebalance()
                continue
            if (gapIdx < target):
                for i in range(gapIdx, target):
                    sparse[i] = sparse[(i + 1)]
                for i in range(len(ordered)):
                    if ((ordered[i] > gapIdx) and (ordered[i] <= target)):
                        ordered[i] -= 1
            elif (gapIdx > target):
                for i in range(gapIdx, target, -1):
                    sparse[i] = sparse[(i - 1)]
                for i in range(len(ordered)):
                    if ((ordered[i] >= target) and (ordered[i] < gapIdx)):
                        ordered[i] += 1
            sparse[target] = v
            ordered.insert(pos, target)
            return

    if (n < 2):
        return
    sparseSize = 1
    while (sparseSize < (n * 2)):
        sparseSize <<= 1
    sparse = [None] * sparseSize
    ordered = []
    for i in range(n):
        insertValue(arr[i])
        compare(i, i)
    for i in range(n):
        arr[i] = sparse[ordered[i]]
        write(i, arr[i])
        markSorted(i)

#include <vector>
#include <algorithm>
int valueAt(int pos);
int lowerBound(int v);
void rebalance();
void insertValue(int v);

int valueAt(int pos) {
    return sparse[ordered[pos]];
}

int lowerBound(int v) {
    int lo = 0;
    int hi = n;
    while((lo < hi)) {
        int mid = ((lo + hi) >> 1);
        if((valueAt(mid) < v)) {
            lo = (mid + 1);
        } else {
            hi = mid;
        }
    }
    return lo;
}

void rebalance() {
    std::vector<int> values(n); for(int _mi=0;_mi<n;_mi++) { int idx=ordered[_mi]; values[_mi]=sparse[idx]; }
    sparseSize <<= 1;
    sparse = std::vector<int>(sparseSize);
    ordered.clear();
    int gap = ((2) > ((sparseSize / ((1) > ((n + 1)) ? (1) : ((n + 1))))) ? (2) : ((sparseSize / ((1) > ((n + 1)) ? (1) : ((n + 1))))));
    int cursor = gap;
    for(int i=0; i<n; i++) {
        int v = values[i];
        if((cursor >= sparseSize)) {
            cursor = (sparseSize - 1);
        }
        sparse[cursor] = v;
        ordered.push_back(cursor);
        cursor += gap;
    }
}

void insertValue(int v) {
    while(1) {
        if((n == 0)) {
            int mid = (sparseSize / 2);
            sparse[mid] = v;
            ordered.push_back(mid);
            return;
        }
        int pos = lowerBound(v);
        int left = (((pos > 0)) ? (ordered[(pos - 1)]) : (-1));
        int right = (((pos < n)) ? (ordered[pos]) : (sparseSize));
        int target = ((left + right) / 2);
        int gapIdx = -1;
        for(int d=0; d<sparseSize; d++) {
            int a = (target - d);
            int b = (target + d);
            if(((a >= 0) && (sparse[a] == 0))) {
                gapIdx = a;
                break;
            }
            if(((b < sparseSize) && (sparse[b] == 0))) {
                gapIdx = b;
                break;
            }
        }
        if((gapIdx == -1)) {
            rebalance();
            continue;
        }
        if((gapIdx < target)) {
            for(int i=gapIdx; i<target; i++) {
                sparse[i] = sparse[(i + 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] > gapIdx) && (ordered[i] <= target))) {
                    ordered[i]--;
                }
            }
        } else if((gapIdx > target)) {
            for(int i=gapIdx; i>target; i--) {
                sparse[i] = sparse[(i - 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] >= target) && (ordered[i] < gapIdx))) {
                    ordered[i]++;
                }
            }
        }
        sparse[target] = v;
        ordered.insert(ordered.begin() + pos, target);
        return;
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int sparseSize = 1;
    while((sparseSize < (n * 2))) {
        sparseSize <<= 1;
    }
    std::vector<int> sparse(sparseSize, 0);
    std::vector<int> ordered;
    for(int i=0; i<n; i++) {
        insertValue(arr[i]);
        compare(i, i);
    }
    for(int i=0; i<n; i++) {
        arr[i] = sparse[ordered[i]];
        write(i, arr[i]);
        markSorted(i);
    }
}

int valueAt(int pos) {
    return sparse[ordered[pos]];
}

int lowerBound(int v) {
    int lo = 0;
    int hi = n;
    while((lo < hi)) {
        int mid = ((lo + hi) >> 1);
        if((valueAt(mid) < v)) {
            lo = (mid + 1);
        } else {
            hi = mid;
        }
    }
    return lo;
}

void rebalance() {
    int[] values = new int[n]; for(int _mi=0;_mi<n;_mi++) { int idx=ordered[_mi]; values[_mi]=sparse[idx]; }
    sparseSize <<= 1;
    sparse = new int[sparseSize];
    ordered_len = 0;
    int gap = Math.Max(2, (sparseSize / Math.Max(1, (n + 1))));
    int cursor = gap;
    for(int i=0; i<n; i++) {
        int v = values[i];
        if((cursor >= sparseSize)) {
            cursor = (sparseSize - 1);
        }
        sparse[cursor] = v;
        ordered[ordered_len++] = cursor;
        cursor += gap;
    }
}

void insertValue(int v) {
    while(true) {
        if((n == 0)) {
            int mid = (sparseSize / 2);
            sparse[mid] = v;
            ordered[ordered_len++] = mid;
            return;
        }
        int pos = lowerBound(v);
        int left = (((pos > 0)) ? (ordered[(pos - 1)]) : (-1));
        int right = (((pos < n)) ? (ordered[pos]) : (sparseSize));
        int target = ((left + right) / 2);
        int gapIdx = -1;
        for(int d=0; d<sparseSize; d++) {
            int a = (target - d);
            int b = (target + d);
            if(((a >= 0) && (sparse[a] == 0))) {
                gapIdx = a;
                break;
            }
            if(((b < sparseSize) && (sparse[b] == 0))) {
                gapIdx = b;
                break;
            }
        }
        if((gapIdx == -1)) {
            rebalance();
            continue;
        }
        if((gapIdx < target)) {
            for(int i=gapIdx; i<target; i++) {
                sparse[i] = sparse[(i + 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] > gapIdx) && (ordered[i] <= target))) {
                    ordered[i]--;
                }
            }
        } else if((gapIdx > target)) {
            for(int i=gapIdx; i>target; i--) {
                sparse[i] = sparse[(i - 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] >= target) && (ordered[i] < gapIdx))) {
                    ordered[i]++;
                }
            }
        }
        sparse[target] = v;
        ordered_insert(pos, target);
        return;
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int sparseSize = 1;
    while((sparseSize < (n * 2))) {
        sparseSize <<= 1;
    }
    int[] sparse = new int[sparseSize];
    var ordered = new List<int>();
    for(int i=0; i<n; i++) {
        insertValue(arr[i]);
        compare(i, i);
    }
    for(int i=0; i<n; i++) {
        arr[i] = sparse[ordered[i]];
        write(i, arr[i]);
        markSorted(i);
    }
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int valueAt(int pos);
int lowerBound(int v);
void rebalance();
void insertValue(int v);

int valueAt(int pos) {
    return sparse[ordered[pos]];
}

int lowerBound(int v) {
    int lo = 0;
    int hi = n;
    while((lo < hi)) {
        int mid = ((lo + hi) >> 1);
        if((valueAt(mid) < v)) {
            lo = (mid + 1);
        } else {
            hi = mid;
        }
    }
    return lo;
}

void rebalance() {
    int* values = (int*)malloc((n) * sizeof(int)); for(int _mi=0;_mi<n;_mi++) { int idx=ordered[_mi]; values[_mi]=sparse[idx]; }
    sparseSize <<= 1;
    sparse = _new_arr_sparseSize;
    ordered_len = 0;
    int gap = ((2) > ((sparseSize / ((1) > ((n + 1)) ? (1) : ((n + 1))))) ? (2) : ((sparseSize / ((1) > ((n + 1)) ? (1) : ((n + 1))))));
    int cursor = gap;
    for(int i=0; i<n; i++) {
        int v = values[i];
        if((cursor >= sparseSize)) {
            cursor = (sparseSize - 1);
        }
        sparse[cursor] = v;
        ordered[ordered_len++] = cursor;
        cursor += gap;
    }
}

void insertValue(int v) {
    while(1) {
        if((n == 0)) {
            int mid = (sparseSize / 2);
            sparse[mid] = v;
            ordered[ordered_len++] = mid;
            return;
        }
        int pos = lowerBound(v);
        int left = (((pos > 0)) ? (ordered[(pos - 1)]) : (-1));
        int right = (((pos < n)) ? (ordered[pos]) : (sparseSize));
        int target = ((left + right) / 2);
        int gapIdx = -1;
        for(int d=0; d<sparseSize; d++) {
            int a = (target - d);
            int b = (target + d);
            if(((a >= 0) && (sparse[a] == 0))) {
                gapIdx = a;
                break;
            }
            if(((b < sparseSize) && (sparse[b] == 0))) {
                gapIdx = b;
                break;
            }
        }
        if((gapIdx == -1)) {
            rebalance();
            continue;
        }
        if((gapIdx < target)) {
            for(int i=gapIdx; i<target; i++) {
                sparse[i] = sparse[(i + 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] > gapIdx) && (ordered[i] <= target))) {
                    ordered[i]--;
                }
            }
        } else if((gapIdx > target)) {
            for(int i=gapIdx; i>target; i--) {
                sparse[i] = sparse[(i - 1)];
            }
            for(int i=0; i<n; i++) {
                if(((ordered[i] >= target) && (ordered[i] < gapIdx))) {
                    ordered[i]++;
                }
            }
        }
        sparse[target] = v;
        ordered_insert(pos, target);
        return;
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int sparseSize = 1;
    while((sparseSize < (n * 2))) {
        sparseSize <<= 1;
    }
    int* sparse = (int*)malloc((sparseSize) * sizeof(int)); memset(sparse, 0, (sparseSize) * sizeof(int));
    int* ordered = (int*)malloc(n * sizeof(int)); int ordered_len = 0;
    for(int i=0; i<n; i++) {
        insertValue(arr[i]);
        compare(i, i);
    }
    for(int i=0; i<n; i++) {
        arr[i] = sparse[ordered[i]];
        write(i, arr[i]);
        markSorted(i);
    }
}