Smoothsort

function smoothSort(arr) {
  const leo = [1, 1];
  while (leo[leo.length-1] < arr.length)
    leo.push(leo.at(-1) + leo.at(-2) + 1);
  let heap = [];  // track Leonardo tree sizes
  for (let i = 0; i < arr.length; i++) {
    // Add element to Leonardo heap
    if (heap.length >= 2 && heap.at(-1) === heap.at(-2) + 1)
      heap[heap.length - 2]++, heap.pop();
    else heap.push(1);
    siftDown(arr, i, heap);
  }
  for (let i = arr.length - 1; i > 0; i--) {
    // Dequeue phase: shrink heap, sift
    if (heap.at(-1) <= 1) heap.pop();
    else { let k = heap.pop();
      heap.push(k - 1, k - 2); siftDown(arr, i, heap); }
  }
}

def smooth_sort(arr):
    leo = [1, 1]
    while leo[-1] < len(arr):
        leo.append(leo[-1] + leo[-2] + 1)
    heap = []
    for i in range(len(arr)):
        if len(heap) >= 2 and heap[-1] == heap[-2] + 1:
            heap[-2] += 1; heap.pop()
        else: heap.append(1)
        sift_down(arr, i, heap)
    for i in range(len(arr)-1, 0, -1):
        if heap[-1] <= 1: heap.pop()
        else:
            k = heap.pop()
            heap.extend([k-1, k-2])
            sift_down(arr, i, heap)

void smoothSort(vector<int>& arr) {
  vector<int> leo = {1, 1};
  while (leo.back() < (int)arr.size())
    leo.push_back(leo[leo.size()-1] + leo[leo.size()-2] + 1);
  vector<int> heap;
  for (int i = 0; i < (int)arr.size(); i++) {
    if (heap.size() >= 2 && heap.back() == heap[heap.size()-2] + 1)
      heap[heap.size()-2]++, heap.pop_back();
    else heap.push_back(1);
    siftDown(arr, i, heap);
  }
  for (int i = arr.size()-1; i > 0; i--) {
    if (heap.back() <= 1) heap.pop_back();
    else { int k = heap.back(); heap.pop_back();
      heap.push_back(k-1); heap.push_back(k-2);
      siftDown(arr, i, heap); }
  }
}

void SmoothSort(int[] arr) {
  var leo = new List<int> { 1, 1 };
  while (leo[^1] < arr.Length)
    leo.Add(leo[^1] + leo[^2] + 1);
  var heap = new List<int>();
  for (int i = 0; i < arr.Length; i++) {
    if (heap.Count >= 2 && heap[^1] == heap[^2] + 1)
      { heap[^2]++; heap.RemoveAt(heap.Count-1); }
    else heap.Add(1);
    SiftDown(arr, i, heap);
  }
  for (int i = arr.Length-1; i > 0; i--) {
    if (heap[^1] <= 1) heap.RemoveAt(heap.Count-1);
    else { int k = heap[^1]; heap.RemoveAt(heap.Count-1);
      heap.Add(k-1); heap.Add(k-2);
      SiftDown(arr, i, heap); }
  }
}

void smoothSort(int arr[], int n) {
  int leo[64], lLen = 2;
  leo[0] = leo[1] = 1;
  while (leo[lLen-1] < n)
    leo[lLen] = leo[lLen-1] + leo[lLen-2] + 1, lLen++;
  int heap[64], hLen = 0;
  for (int i = 0; i < n; i++) {
    if (hLen >= 2 && heap[hLen-1] == heap[hLen-2] + 1)
      heap[hLen-2]++, hLen--;
    else heap[hLen++] = 1;
    siftDown(arr, i, heap, hLen);
  }
  for (int i = n-1; i > 0; i--) {
    if (heap[hLen-1] <= 1) hLen--;
    else { int k = heap[--hLen];
      heap[hLen++] = k-1; heap[hLen++] = k-2;
      siftDown(arr, i, heap, hLen); }
  }
}