Smooth Sort

pick a language to open the code

LEO = [1, 1]
while len(LEO) < 40:
    LEO.append(LEO[-1] + LEO[-2] + 1)


def trinkle(a, orders, j, r):
    k = orders[j]
    while j > 0:
        prev = r - LEO[k]
        big = max(a[r], a[r - 1], a[r - 1 - LEO[k - 2]]) if k >= 2 else a[r]
        if a[prev] <= big:
            break
        a[r], a[prev] = a[prev], a[r]
        j -= 1
        r, k = prev, orders[j]
    while k >= 2:
        left = r - 1 - LEO[k - 2]
        child, step = (r - 1, 2) if a[r - 1] >= a[left] else (left, 1)
        if a[r] >= a[child]:
            return
        a[r], a[child] = a[child], a[r]
        r, k = child, k - step


def smooth_sort(a):
    orders = []
    for i in range(len(a)):
        if len(orders) >= 2 and orders[-2] == orders[-1] + 1:
            orders.pop()
            orders[-1] += 1
        else:
            orders.append(0 if orders and orders[-1] == 1 else 1)
        trinkle(a, orders, len(orders) - 1, i)
    for i in range(len(a) - 1, 0, -1):
        k = orders.pop()
        if k >= 2:
            orders.append(k - 1)
            trinkle(a, orders, len(orders) - 1, i - 1 - LEO[k - 2])
            orders.append(k - 2)
            trinkle(a, orders, len(orders) - 1, i - 1)

const LEO = [1, 1];
while (LEO.length < 40) LEO.push(LEO.at(-1) + LEO.at(-2) + 1);

function trinkle(a, orders, j, r) {
  let k = orders[j];
  while (j > 0) {
    const prev = r - LEO[k];
    let big = a[r];
    if (k >= 2) big = Math.max(big, a[r - 1], a[r - 1 - LEO[k - 2]]);
    if (a[prev] <= big) break;
    [a[r], a[prev]] = [a[prev], a[r]];
    [r, k] = [prev, orders[--j]];
  }
  while (k >= 2) {
    const left = r - 1 - LEO[k - 2];
    const child = a[r - 1] >= a[left] ? r - 1 : left;
    if (a[r] >= a[child]) return;
    [a[r], a[child]] = [a[child], a[r]];
    k -= child === r - 1 ? 2 : 1;
    r = child;
  }
}

function smoothSort(a) {
  const orders = [];
  for (let i = 0; i < a.length; i++) {
    if (orders.length >= 2 && orders.at(-2) === orders.at(-1) + 1) {
      orders.pop();
      orders[orders.length - 1]++;
    } else {
      orders.push(orders.at(-1) === 1 ? 0 : 1);
    }
    trinkle(a, orders, orders.length - 1, i);
  }
  for (let i = a.length - 1; i > 0; i--) {
    const k = orders.pop();
    if (k < 2) continue;
    orders.push(k - 1);
    trinkle(a, orders, orders.length - 1, i - 1 - LEO[k - 2]);
    orders.push(k - 2);
    trinkle(a, orders, orders.length - 1, i - 1);
  }
}

static const int LEO[] = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465,
    753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735};

static void trinkle(int a[], int orders[], int j, int r) {
    int k = orders[j];
    while (j > 0) {
        int prev = r - LEO[k];
        int big = a[r];
        if (k >= 2 && a[r - 1] > big) big = a[r - 1];
        if (k >= 2 && a[r - 1 - LEO[k - 2]] > big) big = a[r - 1 - LEO[k - 2]];
        if (a[prev] <= big) break;
        int t = a[r]; a[r] = a[prev]; a[prev] = t;
        r = prev;
        k = orders[--j];
    }
    while (k >= 2) {
        int left = r - 1 - LEO[k - 2];
        int child = a[r - 1] >= a[left] ? r - 1 : left;
        if (a[r] >= a[child]) return;
        int t = a[r]; a[r] = a[child]; a[child] = t;
        k -= child == r - 1 ? 2 : 1;
        r = child;
    }
}

void smooth_sort(int a[], int n) {
    int orders[24];
    int top = -1;
    for (int i = 0; i < n; i++) {
        if (top >= 1 && orders[top - 1] == orders[top] + 1) orders[--top]++;
        else if (top >= 0 && orders[top] == 1) orders[++top] = 0;
        else orders[++top] = 1;
        trinkle(a, orders, top, i);
    }
    for (int i = n - 1; i > 0; i--) {
        int k = orders[top--];
        if (k < 2) continue;
        orders[++top] = k - 1;
        trinkle(a, orders, top, i - 1 - LEO[k - 2]);
        orders[++top] = k - 2;
        trinkle(a, orders, top, i - 1);
    }
}

static const int LEO[] = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465,
    753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735};

static void trinkle(std::vector<int>& a, const int orders[], int j, int r) {
    int k = orders[j];
    while (j > 0) {
        int prev = r - LEO[k];
        int big = a[r];
        if (k >= 2) big = std::max({big, a[r - 1], a[r - 1 - LEO[k - 2]]});
        if (a[prev] <= big) break;
        std::swap(a[r], a[prev]);
        r = prev;
        k = orders[--j];
    }
    while (k >= 2) {
        int left = r - 1 - LEO[k - 2];
        int child = a[r - 1] >= a[left] ? r - 1 : left;
        if (a[r] >= a[child]) return;
        std::swap(a[r], a[child]);
        k -= child == r - 1 ? 2 : 1;
        r = child;
    }
}

void smooth_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    int orders[24];
    int top = -1;
    for (int i = 0; i < n; i++) {
        if (top >= 1 && orders[top - 1] == orders[top] + 1) orders[--top]++;
        else if (top >= 0 && orders[top] == 1) orders[++top] = 0;
        else orders[++top] = 1;
        trinkle(a, orders, top, i);
    }
    for (int i = n - 1; i > 0; i--) {
        int k = orders[top--];
        if (k < 2) continue;
        orders[++top] = k - 1;
        trinkle(a, orders, top, i - 1 - LEO[k - 2]);
        orders[++top] = k - 2;
        trinkle(a, orders, top, i - 1);
    }
}

static readonly int[] Leo = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287,
    465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735};

static void Trinkle(int[] a, int[] orders, int j, int r) {
    int k = orders[j];
    while (j > 0) {
        int prev = r - Leo[k];
        int big = a[r];
        if (k >= 2) big = Math.Max(big, a[r - 1]);
        if (k >= 2) big = Math.Max(big, a[r - 1 - Leo[k - 2]]);
        if (a[prev] <= big) break;
        (a[r], a[prev]) = (a[prev], a[r]);
        r = prev;
        k = orders[--j];
    }
    while (k >= 2) {
        int left = r - 1 - Leo[k - 2];
        int child = a[r - 1] >= a[left] ? r - 1 : left;
        if (a[r] >= a[child]) return;
        (a[r], a[child]) = (a[child], a[r]);
        k -= child == r - 1 ? 2 : 1;
        r = child;
    }
}

static void SmoothSort(int[] a) {
    int[] orders = new int[Leo.Length];
    int top = -1;
    for (int i = 0; i < a.Length; i++) {
        if (top >= 1 && orders[top - 1] == orders[top] + 1) orders[--top]++;
        else if (top >= 0 && orders[top] == 1) orders[++top] = 0;
        else orders[++top] = 1;
        Trinkle(a, orders, top, i);
    }
    for (int i = a.Length - 1; i > 0; i--) {
        int k = orders[top--];
        if (k < 2) continue;
        orders[++top] = k - 1;
        Trinkle(a, orders, top, i - 1 - Leo[k - 2]);
        orders[++top] = k - 2;
        Trinkle(a, orders, top, i - 1);
    }
}

static final int[] LEO = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465,
    753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735};

static void trinkle(int[] a, int[] orders, int j, int r) {
    int k = orders[j];
    while (j > 0) {
        int prev = r - LEO[k];
        int big = a[r];
        if (k >= 2) big = Math.max(big, a[r - 1]);
        if (k >= 2) big = Math.max(big, a[r - 1 - LEO[k - 2]]);
        if (a[prev] <= big) break;
        int t = a[r]; a[r] = a[prev]; a[prev] = t;
        r = prev;
        k = orders[--j];
    }
    while (k >= 2) {
        int left = r - 1 - LEO[k - 2];
        int child = a[r - 1] >= a[left] ? r - 1 : left;
        if (a[r] >= a[child]) return;
        int t = a[r]; a[r] = a[child]; a[child] = t;
        k -= child == r - 1 ? 2 : 1;
        r = child;
    }
}

static void smoothSort(int[] a) {
    int[] orders = new int[LEO.length];
    int top = -1;
    for (int i = 0; i < a.length; i++) {
        if (top >= 1 && orders[top - 1] == orders[top] + 1) orders[--top]++;
        else if (top >= 0 && orders[top] == 1) orders[++top] = 0;
        else orders[++top] = 1;
        trinkle(a, orders, top, i);
    }
    for (int i = a.length - 1; i > 0; i--) {
        int k = orders[top--];
        if (k < 2) continue;
        orders[++top] = k - 1;
        trinkle(a, orders, top, i - 1 - LEO[k - 2]);
        orders[++top] = k - 2;
        trinkle(a, orders, top, i - 1);
    }
}