自底向上归并排序

选一种语言就能看到代码

def bottom_up_merge_sort(a):
    n = len(a)
    width = 1
    while width < n:
        for lo in range(0, n, 2 * width):
            mid = min(lo + width, n)
            hi = min(lo + 2 * width, n)
            merged = []
            i, j = lo, mid
            while i < mid and j < hi:
                if a[i] <= a[j]:
                    merged.append(a[i])
                    i += 1
                else:
                    merged.append(a[j])
                    j += 1
            merged.extend(a[i:mid])
            merged.extend(a[j:hi])
            a[lo:hi] = merged
        width *= 2

function bottomUpMergeSort(a) {
  const n = a.length;
  const buf = new Array(n);
  for (let width = 1; 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);
      let i = lo;
      let j = mid;
      let k = lo;
      while (i < mid && j < hi) buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
      while (i < mid) buf[k++] = a[i++];
      while (j < hi) buf[k++] = a[j++];
    }
    for (let i = 0; i < n; i++) a[i] = buf[i];
  }
}

void bottom_up_merge_sort(int a[], int n) {
    int* buf = malloc(sizeof(int) * (n + 1));
    for (int width = 1; 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;
            int i = lo, j = mid, k = lo;
            while (i < mid && j < hi) {
                buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            }
            while (i < mid) buf[k++] = a[i++];
            while (j < hi) buf[k++] = a[j++];
        }
        memcpy(a, buf, sizeof(int) * n);
    }
    free(buf);
}

void bottom_up_merge_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    std::vector<int> buf(a.size());
    for (int width = 1; 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);
            std::merge(a.begin() + lo, a.begin() + mid, a.begin() + mid,
                       a.begin() + hi, buf.begin() + lo);
        }
        a = buf;
    }
}

static void BottomUpMergeSort(int[] a) {
    int n = a.Length;
    int[] buf = new int[n];
    for (int width = 1; 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);
            int i = lo, j = mid, k = lo;
            while (i < mid && j < hi) {
                buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            }
            while (i < mid) buf[k++] = a[i++];
            while (j < hi) buf[k++] = a[j++];
        }
        Array.Copy(buf, a, n);
    }
}

static void bottomUpMergeSort(int[] a) {
    int n = a.length;
    int[] buf = new int[n];
    for (int width = 1; 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);
            int i = lo, j = mid, k = lo;
            while (i < mid && j < hi) {
                buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            }
            while (i < mid) buf[k++] = a[i++];
            while (j < hi) buf[k++] = a[j++];
        }
        System.arraycopy(buf, 0, a, 0, n);
    }
}