蒂姆排序

选一种语言就能看到代码

RUN = 32


def tim_sort(a):
    n = len(a)
    for lo in range(0, n, RUN):
        insertion_sort_range(a, lo, min(lo + RUN, n))
    width = RUN
    while width < n:
        for lo in range(0, n, 2 * width):
            mid = min(lo + width, n)
            hi = min(lo + 2 * width, n)
            if mid < hi:
                merge(a, lo, mid, hi)
        width *= 2

const RUN = 32;

function timSort(a) {
  const n = a.length;
  for (let lo = 0; lo < n; lo += RUN) {
    insertionSortRange(a, lo, Math.min(lo + RUN, n));
  }
  for (let width = RUN; width < n; width *= 2) {
    for (let lo = 0; lo < n; lo += 2 * width) {
      const mid = Math.min(lo + width, n);
      const hi = Math.min(lo + 2 * width, n);
      if (mid < hi) merge(a, lo, mid, hi);
    }
  }
}

#define RUN 32

void tim_sort(int a[], int n, int buf[]) {
    for (int lo = 0; lo < n; lo += RUN) {
        int hi = lo + RUN < n ? lo + RUN : n;
        insertion_sort_range(a, lo, hi);
    }
    for (int width = RUN; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = lo + width < n ? lo + width : n;
            int hi = lo + 2 * width < n ? lo + 2 * width : n;
            if (mid < hi) merge(a, lo, mid, hi, buf);
        }
    }
}

constexpr int RUN = 32;

void tim_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int lo = 0; lo < n; lo += RUN) {
        insertion_sort_range(a, lo, std::min(lo + RUN, n));
    }
    for (int width = RUN; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = std::min(lo + width, n);
            int hi = std::min(lo + 2 * width, n);
            if (mid < hi) std::inplace_merge(a.begin() + lo,
                                             a.begin() + mid,
                                             a.begin() + hi);
        }
    }
}

const int Run = 32;

static void TimSort(int[] a, int[] buf) {
    int n = a.Length;
    for (int lo = 0; lo < n; lo += Run) {
        InsertionSortRange(a, lo, Math.Min(lo + Run, n));
    }
    for (int width = Run; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = Math.Min(lo + width, n);
            int hi = Math.Min(lo + 2 * width, n);
            if (mid < hi) Merge(a, lo, mid, hi, buf);
        }
    }
}

static final int RUN = 32;

static void timSort(int[] a, int[] buf) {
    int n = a.length;
    for (int lo = 0; lo < n; lo += RUN) {
        insertionSortRange(a, lo, Math.min(lo + RUN, n));
    }
    for (int width = RUN; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = Math.min(lo + width, n);
            int hi = Math.min(lo + 2 * width, n);
            if (mid < hi) merge(a, lo, mid, hi, buf);
        }
    }
}