归并排序

选一种语言就能看到代码

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));
  const right = mergeSort(a.slice(mid));
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

static void merge(int a[], int lo, int mid, int hi, int buf[]) {
    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++];
    for (int t = lo; t < hi; t++) a[t] = buf[t];
}

void merge_sort(int a[], int lo, int hi, int buf[]) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid, buf);
    merge_sort(a, mid, hi, buf);
    merge(a, lo, mid, hi, buf);
}

void merge_sort(std::vector<int>& a, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid, hi);

    std::vector<int> buf;
    buf.reserve(hi - lo);
    int i = lo, j = mid;
    while (i < mid && j < hi) {
        buf.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    }
    while (i < mid) buf.push_back(a[i++]);
    while (j < hi) buf.push_back(a[j++]);
    std::copy(buf.begin(), buf.end(), a.begin() + lo);
}

static void MergeSort(int[] a, int lo, int hi, int[] buf) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    MergeSort(a, lo, mid, buf);
    MergeSort(a, mid, hi, buf);

    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, lo, a, lo, hi - lo);
}

static void mergeSort(int[] a, int lo, int hi, int[] buf) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, buf);
    mergeSort(a, mid, hi, buf);

    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, lo, a, lo, hi - lo);
}