Library Sort

function librarySort(arr) {
  const n = arr.length;
  const gaps = new Array(2 * n + 1).fill(null);
  gaps[1] = arr[0];
  let gLen = 1;
  for (let i = 1; i < n; i++) {
    // Binary search in gapped array
    let pos = binarySearch(gaps, gLen, arr[i]);
    insert(gaps, pos, arr[i]);
    gLen++;
    if (gLen >= gaps.length / 2) rebalance(gaps);
  }
  // Compact gaps back into arr
}

def library_sort(arr):
    n = len(arr)
    gaps = [None] * (2 * n + 1)
    gaps[1] = arr[0]
    g_len = 1
    for i in range(1, n):
        pos = binary_search(gaps, g_len, arr[i])
        insert_at(gaps, pos, arr[i])
        g_len += 1
        if g_len >= len(gaps) // 2:
            rebalance(gaps)
    # Compact non-None values back into arr

void librarySort(vector<int>& arr) {
  int n = arr.size();
  vector<optional<int>> gaps(2*n+1, nullopt);
  gaps[1] = arr[0]; int gLen = 1;
  for (int i = 1; i < n; i++) {
    int pos = binarySearch(gaps, gLen, arr[i]);
    insertAt(gaps, pos, arr[i]);
    gLen++;
    if (gLen >= (int)gaps.size() / 2)
      rebalance(gaps);
  }
  // Compact non-nullopt values back into arr
}

void LibrarySort(int[] arr) {
  int n = arr.Length;
  int?[] gaps = new int?[2 * n + 1];
  gaps[1] = arr[0]; int gLen = 1;
  for (int i = 1; i < n; i++) {
    int pos = BinarySearch(gaps, gLen, arr[i]);
    Insert(gaps, pos, arr[i]);
    gLen++;
    if (gLen >= gaps.Length / 2)
      Rebalance(gaps);
  }
  // Compact non-null values back into arr
}

void librarySort(int arr[], int n) {
  int gaps[2 * n + 1];
  int used[2 * n + 1];
  memset(used, 0, sizeof(used));
  gaps[1] = arr[0]; used[1] = 1;
  int gLen = 1;
  for (int i = 1; i < n; i++) {
    int pos = binarySearch(gaps, used, gLen, arr[i]);
    insertAt(gaps, used, pos, arr[i]);
    gLen++;
    if (gLen >= n) rebalance(gaps, used, 2*n+1);
  }
  // Compact into arr
}