Smoothsort

function smoothSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) {
      markSorted(0);
      checkpoint(100, 100);
    }
    return;
  }
  const leo = [1, 1];
  while (leo[leo.length - 1] < n) {
    leo.push(leo[leo.length - 1] + leo[leo.length - 2] + 1);
  }
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.leonardoOrders = leo.length;
  function swapIndices(left, right) {
    if (left === right) return;
    const value = arr[left];
    arr[left] = arr[right];
    arr[right] = value;
    recordMetric('swapOperations');
    swap(left, right);
  }
  function markSorted(index, completed) {
    markSorted(index);
    checkpoint(40 + Math.floor(completed * 60 / n), 100);
  }
  function sift(root, order) {
    recordMetric('siftCalls');
    while (order >= 2) {
      const rightChild = root - 1;
      const leftChild = root - 1 - leo[order - 2];
      let largest = root;
      recordMetric('rootChildComparisons');
      compare(leftChild, largest);
      if (arr[leftChild] > arr[largest]) largest = leftChild;
      recordMetric('rootChildComparisons');
      compare(rightChild, largest);
      if (arr[rightChild] > arr[largest]) largest = rightChild;
      if (largest === root) break;
      swapIndices(root, largest);
      recordMetric('siftDescents');
      if (largest === leftChild) {
        root = leftChild;
        order -= 1;
      } else {
        root = rightChild;
        order -= 2;
      }
    }
  }
  const orders = [];
  function trinkle(pos, idx) {
    recordMetric('trinkleCalls');
    while (idx > 0) {
      const prevPos = pos - leo[orders[idx]];
      recordMetric('ancestorComparisons');
      compare(prevPos, pos);
      if (arr[prevPos] <= arr[pos]) break;
      if (orders[idx] >= 2) {
        const rightChild = pos - 1;
        const leftChild = pos - 1 - leo[orders[idx] - 2];
        recordMetric('childGuardComparisons');
        compare(prevPos, leftChild);
        if (arr[prevPos] <= arr[leftChild]) break;
        recordMetric('childGuardComparisons');
        compare(prevPos, rightChild);
        if (arr[prevPos] <= arr[rightChild]) break;
      }
      swapIndices(pos, prevPos);
      recordMetric('trinkleAscents');
      pos = prevPos;
      idx--;
    }
    sift(pos, orders[idx]);
  }
  for (let i = 0; i < n; i++) {
    const heapCount = orders.length;
    if (heapCount >= 2 && orders[heapCount - 2] === orders[heapCount - 1] + 1) {
      orders.pop();
      orders[orders.length - 1]++;
      recordMetric('heapMerges');
    } else if (heapCount >= 1 && orders[heapCount - 1] === 1) {
      orders.push(0);
      recordMetric('heapPushes');
    } else {
      orders.push(1);
      recordMetric('heapPushes');
    }
    trinkle(i, orders.length - 1);
    checkpoint(Math.floor((i + 1) * 40 / n), 100);
  }
  let completed = 0;
  for (let i = n - 1; i > 0; i--) {
    completed++;
    recordMetric('extractionPasses');
    markSorted(i, completed);
    if (orders[orders.length - 1] <= 1) {
      orders.pop();
    } else {
      const order = orders.pop();
      const rightPos = i - 1;
      const leftPos = i - 1 - leo[order - 2];
      orders.push(order - 1);
      recordMetric('heapSplits');
      trinkle(leftPos, orders.length - 1);
      orders.push(order - 2);
      recordMetric('heapSplits');
      trinkle(rightPos, orders.length - 1);
    }
  }
  markSorted(0);
  checkpoint(100, 100);
}

def smoothSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def swapIndices(left, right):
        if (left == right):
            return
        value = arr[left]
        arr[left] = arr[right]
        arr[right] = value
        recordMetric("swapOperations")
        swap(left, right)

    def markSorted(index, completed):
        markSorted(index)
        checkpoint((40 + int((completed * 60) / n)), 100)

    def sift(root, order):
        recordMetric("siftCalls")
        while (order >= 2):
            rightChild = (root - 1)
            leftChild = ((root - 1) - leo[(order - 2)])
            largest = root
            recordMetric("rootChildComparisons")
            compare(leftChild, largest)
            if (arr[leftChild] > arr[largest]):
                largest = leftChild
            recordMetric("rootChildComparisons")
            compare(rightChild, largest)
            if (arr[rightChild] > arr[largest]):
                largest = rightChild
            if (largest == root):
                break
            swapIndices(root, largest)
            recordMetric("siftDescents")
            if (largest == leftChild):
                root = leftChild
                order -= 1
            else:
                root = rightChild
                order -= 2

    def trinkle(pos, idx):
        recordMetric("trinkleCalls")
        while (idx > 0):
            prevPos = (pos - leo[orders[idx]])
            recordMetric("ancestorComparisons")
            compare(prevPos, pos)
            if (arr[prevPos] <= arr[pos]):
                break
            if (orders[idx] >= 2):
                rightChild = (pos - 1)
                leftChild = ((pos - 1) - leo[(orders[idx] - 2)])
                recordMetric("childGuardComparisons")
                compare(prevPos, leftChild)
                if (arr[prevPos] <= arr[leftChild]):
                    break
                recordMetric("childGuardComparisons")
                compare(prevPos, rightChild)
                if (arr[prevPos] <= arr[rightChild]):
                    break
            swapIndices(pos, prevPos)
            recordMetric("trinkleAscents")
            pos = prevPos
            idx -= 1
        sift(pos, orders[idx])

    if (n < 2):
        if (n == 1):
            markSorted(0)
            checkpoint(100, 100)
        return
    leo = [1, 1]
    while (leo[(len(leo) - 1)] < n):
        leo.append(((leo[(len(leo) - 1)] + leo[(len(leo) - 2)]) + 1))
    metrics.leonardoOrders = len(leo)
    orders = []
    for i in range(n):
        heapCount = len(orders)
        if ((heapCount >= 2) and (orders[(heapCount - 2)] == (orders[(heapCount - 1)] + 1))):
            orders.pop()
            orders[(len(orders) - 1)] += 1
            recordMetric("heapMerges")
        elif ((heapCount >= 1) and (orders[(heapCount - 1)] == 1)):
            orders.append(0)
            recordMetric("heapPushes")
        else:
            orders.append(1)
            recordMetric("heapPushes")
        trinkle(i, (len(orders) - 1))
        checkpoint(int(((i + 1) * 40) / n), 100)
    completed = 0
    for i in range((n - 1), 0, -1):
        completed += 1
        recordMetric("extractionPasses")
        markSorted(i, completed)
        if (orders[(len(orders) - 1)] <= 1):
            orders.pop()
        else:
            order = orders.pop()
            rightPos = (i - 1)
            leftPos = ((i - 1) - leo[(order - 2)])
            orders.append((order - 1))
            recordMetric("heapSplits")
            trinkle(leftPos, (len(orders) - 1))
            orders.append((order - 2))
            recordMetric("heapSplits")
            trinkle(rightPos, (len(orders) - 1))
    markSorted(0)
    checkpoint(100, 100)

#include <vector>
#include <algorithm>
void recordMetric(int name, int );
void swapIndices(int left, int right);
void markSorted(int index, int completed);
void sift(int root, int order);
void trinkle(int pos, int idx);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swapIndices(int left, int right) {
    if((left == right)) {
        return;
    }
    int value = arr[left];
    arr[left] = arr[right];
    arr[right] = value;
    recordMetric("swapOperations");
    swap(left, right);
}

void markSorted(int index, int completed) {
    markSorted(index);
    checkpoint((40 + ((completed * 60) / n)), 100);
}

void sift(int root, int order) {
    recordMetric("siftCalls");
    while((order >= 2)) {
        int rightChild = (root - 1);
        int leftChild = ((root - 1) - leo[(order - 2)]);
        int largest = root;
        recordMetric("rootChildComparisons");
        compare(leftChild, largest);
        if((arr[leftChild] > arr[largest])) {
            largest = leftChild;
        }
        recordMetric("rootChildComparisons");
        compare(rightChild, largest);
        if((arr[rightChild] > arr[largest])) {
            largest = rightChild;
        }
        if((largest == root)) {
            break;
        }
        swapIndices(root, largest);
        recordMetric("siftDescents");
        if((largest == leftChild)) {
            root = leftChild;
            order -= 1;
        } else {
            root = rightChild;
            order -= 2;
        }
    }
}

void trinkle(int pos, int idx) {
    recordMetric("trinkleCalls");
    while((idx > 0)) {
        int prevPos = (pos - leo[orders[idx]]);
        recordMetric("ancestorComparisons");
        compare(prevPos, pos);
        if((arr[prevPos] <= arr[pos])) {
            break;
        }
        if((orders[idx] >= 2)) {
            int rightChild = (pos - 1);
            int leftChild = ((pos - 1) - leo[(orders[idx] - 2)]);
            recordMetric("childGuardComparisons");
            compare(prevPos, leftChild);
            if((arr[prevPos] <= arr[leftChild])) {
                break;
            }
            recordMetric("childGuardComparisons");
            compare(prevPos, rightChild);
            if((arr[prevPos] <= arr[rightChild])) {
                break;
            }
        }
        swapIndices(pos, prevPos);
        recordMetric("trinkleAscents");
        pos = prevPos;
        idx--;
    }
    sift(pos, orders[idx]);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
            checkpoint(100, 100);
        }
        return;
    }
    std::vector<int> leo = {1, 1};
    while((leo[((int)leo.size() - 1)] < n)) {
        leo.push_back(((leo[((int)leo.size() - 1)] + leo[((int)leo.size() - 2)]) + 1));
    }
    int metrics = educational.metrics;
    metrics.leonardoOrders = (int)leo.size();
    std::vector<int> orders;
    for(int i=0; i<n; i++) {
        int heapCount = (int)orders.size();
        if(((heapCount >= 2) && (orders[(heapCount - 2)] == (orders[(heapCount - 1)] + 1)))) {
            orders.back();
            orders[((int)orders.size() - 1)]++;
            recordMetric("heapMerges");
        } else if(((heapCount >= 1) && (orders[(heapCount - 1)] == 1))) {
            orders.push_back(0);
            recordMetric("heapPushes");
        } else {
            orders.push_back(1);
            recordMetric("heapPushes");
        }
        trinkle(i, ((int)orders.size() - 1));
        checkpoint((((i + 1) * 40) / n), 100);
    }
    int completed = 0;
    for(int i=(n - 1); i>0; i--) {
        completed++;
        recordMetric("extractionPasses");
        markSorted(i, completed);
        if((orders[((int)orders.size() - 1)] <= 1)) {
            orders.back();
        } else {
            int order = orders.back();
            int rightPos = (i - 1);
            int leftPos = ((i - 1) - leo[(order - 2)]);
            orders.push_back((order - 1));
            recordMetric("heapSplits");
            trinkle(leftPos, ((int)orders.size() - 1));
            orders.push_back((order - 2));
            recordMetric("heapSplits");
            trinkle(rightPos, ((int)orders.size() - 1));
        }
    }
    markSorted(0);
    checkpoint(100, 100);
}

int _listPop(List<int> _l) { int _v = _l[_l.Count - 1]; _l.RemoveAt(_l.Count - 1); return _v; }

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swapIndices(int left, int right) {
    if((left == right)) {
        return;
    }
    int value = arr[left];
    arr[left] = arr[right];
    arr[right] = value;
    recordMetric("swapOperations");
    swap(left, right);
}

void markSorted(int index, int completed) {
    markSorted(index);
    checkpoint((40 + ((completed * 60) / n)), 100);
}

void sift(int root, int order) {
    recordMetric("siftCalls");
    while((order >= 2)) {
        int rightChild = (root - 1);
        int leftChild = ((root - 1) - leo[(order - 2)]);
        int largest = root;
        recordMetric("rootChildComparisons");
        compare(leftChild, largest);
        if((arr[leftChild] > arr[largest])) {
            largest = leftChild;
        }
        recordMetric("rootChildComparisons");
        compare(rightChild, largest);
        if((arr[rightChild] > arr[largest])) {
            largest = rightChild;
        }
        if((largest == root)) {
            break;
        }
        swapIndices(root, largest);
        recordMetric("siftDescents");
        if((largest == leftChild)) {
            root = leftChild;
            order -= 1;
        } else {
            root = rightChild;
            order -= 2;
        }
    }
}

void trinkle(int pos, int idx) {
    recordMetric("trinkleCalls");
    while((idx > 0)) {
        int prevPos = (pos - leo[orders[idx]]);
        recordMetric("ancestorComparisons");
        compare(prevPos, pos);
        if((arr[prevPos] <= arr[pos])) {
            break;
        }
        if((orders[idx] >= 2)) {
            int rightChild = (pos - 1);
            int leftChild = ((pos - 1) - leo[(orders[idx] - 2)]);
            recordMetric("childGuardComparisons");
            compare(prevPos, leftChild);
            if((arr[prevPos] <= arr[leftChild])) {
                break;
            }
            recordMetric("childGuardComparisons");
            compare(prevPos, rightChild);
            if((arr[prevPos] <= arr[rightChild])) {
                break;
            }
        }
        swapIndices(pos, prevPos);
        recordMetric("trinkleAscents");
        pos = prevPos;
        idx--;
    }
    sift(pos, orders[idx]);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
            checkpoint(100, 100);
        }
        return;
    }
    var leo = new List<int> { 1, 1 };
    while((leo[(leo.Count - 1)] < n)) {
        leo.Add(((leo[(leo.Count - 1)] + leo[(leo.Count - 2)]) + 1));
    }
    int metrics = stats.educational.metrics;
    metrics.leonardoOrders = leo.Count;
    var orders = new List<int>();
    for(int i=0; i<n; i++) {
        int heapCount = orders.Count;
        if(((heapCount >= 2) && (orders[(heapCount - 2)] == (orders[(heapCount - 1)] + 1)))) {
            _listPop(orders);
            orders[(orders.Count - 1)]++;
            recordMetric("heapMerges");
        } else if(((heapCount >= 1) && (orders[(heapCount - 1)] == 1))) {
            orders.Add(0);
            recordMetric("heapPushes");
        } else {
            orders.Add(1);
            recordMetric("heapPushes");
        }
        trinkle(i, (orders.Count - 1));
        checkpoint((((i + 1) * 40) / n), 100);
    }
    int completed = 0;
    for(int i=(n - 1); i>0; i--) {
        completed++;
        recordMetric("extractionPasses");
        markSorted(i, completed);
        if((orders[(orders.Count - 1)] <= 1)) {
            _listPop(orders);
        } else {
            int order = _listPop(orders);
            int rightPos = (i - 1);
            int leftPos = ((i - 1) - leo[(order - 2)]);
            orders.Add((order - 1));
            recordMetric("heapSplits");
            trinkle(leftPos, (orders.Count - 1));
            orders.Add((order - 2));
            recordMetric("heapSplits");
            trinkle(rightPos, (orders.Count - 1));
        }
    }
    markSorted(0);
    checkpoint(100, 100);
}

#include <stdio.h>
#include <stdlib.h>
void recordMetric(int name, int );
void swapIndices(int left, int right);
void markSorted(int index, int completed);
void sift(int root, int order);
void trinkle(int pos, int idx);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swapIndices(int left, int right) {
    if((left == right)) {
        return;
    }
    int value = arr[left];
    arr[left] = arr[right];
    arr[right] = value;
    recordMetric("swapOperations");
    swap(left, right);
}

void markSorted(int index, int completed) {
    markSorted(index);
    checkpoint((40 + ((completed * 60) / n)), 100);
}

void sift(int root, int order) {
    recordMetric("siftCalls");
    while((order >= 2)) {
        int rightChild = (root - 1);
        int leftChild = ((root - 1) - leo[(order - 2)]);
        int largest = root;
        recordMetric("rootChildComparisons");
        compare(leftChild, largest);
        if((arr[leftChild] > arr[largest])) {
            largest = leftChild;
        }
        recordMetric("rootChildComparisons");
        compare(rightChild, largest);
        if((arr[rightChild] > arr[largest])) {
            largest = rightChild;
        }
        if((largest == root)) {
            break;
        }
        swapIndices(root, largest);
        recordMetric("siftDescents");
        if((largest == leftChild)) {
            root = leftChild;
            order -= 1;
        } else {
            root = rightChild;
            order -= 2;
        }
    }
}

void trinkle(int pos, int idx) {
    recordMetric("trinkleCalls");
    while((idx > 0)) {
        int prevPos = (pos - leo[orders[idx]]);
        recordMetric("ancestorComparisons");
        compare(prevPos, pos);
        if((arr[prevPos] <= arr[pos])) {
            break;
        }
        if((orders[idx] >= 2)) {
            int rightChild = (pos - 1);
            int leftChild = ((pos - 1) - leo[(orders[idx] - 2)]);
            recordMetric("childGuardComparisons");
            compare(prevPos, leftChild);
            if((arr[prevPos] <= arr[leftChild])) {
                break;
            }
            recordMetric("childGuardComparisons");
            compare(prevPos, rightChild);
            if((arr[prevPos] <= arr[rightChild])) {
                break;
            }
        }
        swapIndices(pos, prevPos);
        recordMetric("trinkleAscents");
        pos = prevPos;
        idx--;
    }
    sift(pos, orders[idx]);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
            checkpoint(100, 100);
        }
        return;
    }
    int* leo = (int*)malloc(n * sizeof(int)); int leo_len = 2;
    leo[0] = 1;
    leo[1] = 1;
    while((leo[(leo_len - 1)] < n)) {
        leo[leo_len++] = ((leo[(leo_len - 1)] + leo[(leo_len - 2)]) + 1);
    }
    int metrics = (*educational).metrics;
    metrics.leonardoOrders = leo_len;
    int* orders = (int*)malloc(n * sizeof(int)); int orders_len = 0;
    for(int i=0; i<n; i++) {
        int heapCount = orders_len;
        if(((heapCount >= 2) && (orders[(heapCount - 2)] == (orders[(heapCount - 1)] + 1)))) {
            orders[--orders_len];
            orders[(orders_len - 1)]++;
            recordMetric("heapMerges");
        } else if(((heapCount >= 1) && (orders[(heapCount - 1)] == 1))) {
            orders[orders_len++] = 0;
            recordMetric("heapPushes");
        } else {
            orders[orders_len++] = 1;
            recordMetric("heapPushes");
        }
        trinkle(i, (orders_len - 1));
        checkpoint((((i + 1) * 40) / n), 100);
    }
    int completed = 0;
    for(int i=(n - 1); i>0; i--) {
        completed++;
        recordMetric("extractionPasses");
        markSorted(i, completed);
        if((orders[(orders_len - 1)] <= 1)) {
            orders[--orders_len];
        } else {
            int order = orders[--orders_len];
            int rightPos = (i - 1);
            int leftPos = ((i - 1) - leo[(order - 2)]);
            orders[orders_len++] = (order - 1);
            recordMetric("heapSplits");
            trinkle(leftPos, (orders_len - 1));
            orders[orders_len++] = (order - 2);
            recordMetric("heapSplits");
            trinkle(rightPos, (orders_len - 1));
        }
    }
    markSorted(0);
    checkpoint(100, 100);
}