Sắp xếp trộn (Merge Sort)

// Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
// halves into one. A single scratch buffer, allocated once, holds the halves while they merge.

/**
 * Sorts `values` in ascending order, in place.
 * Stable: equal values keep the order they started in.
 *
 * @param {number[]} values the array to sort
 * @returns {void}
 */
export function mergeSort(values) {
  const buffer = new Array(values.length); // shared by every merge — never allocated again
  sortRange(values, buffer, 0, values.length);
}

/**
 * Sorts values[lo..hi) — lo included, hi excluded.
 *
 * @param {number[]} values
 * @param {number[]} buffer scratch space, at least as long as `values`
 * @param {number} lo
 * @param {number} hi
 */
function sortRange(values, buffer, lo, hi) {
  if (hi - lo < 2) return; // zero or one value: already sorted

  const mid = lo + Math.floor((hi - lo) / 2);
  sortRange(values, buffer, lo, mid); // left half:  [lo, mid)
  sortRange(values, buffer, mid, hi); // right half: [mid, hi)
  mergeHalves(values, buffer, lo, mid, hi);
}

/**
 * Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi).
 *
 * @param {number[]} values
 * @param {number[]} buffer
 * @param {number} lo
 * @param {number} mid
 * @param {number} hi
 */
function mergeHalves(values, buffer, lo, mid, hi) {
  for (let k = lo; k < hi; k++) buffer[k] = values[k]; // set both halves aside

  let i = lo; // next unused value of the left half
  let j = mid; // next unused value of the right half
  let k = lo; // next slot to fill in values

  while (i < mid && j < hi) {
    // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
    if (buffer[i] <= buffer[j]) {
      values[k++] = buffer[i++];
    } else {
      values[k++] = buffer[j++];
    }
  }
  while (i < mid) values[k++] = buffer[i++];
  // Whatever is left of the right half is already in place: k has caught up with j.
}

# Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
# halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
from typing import List


def merge_sort(values: List[int]) -> None:
    """Sort values in ascending order, in place.

    Stable: equal values keep the order they started in.
    """
    buffer = [0] * len(values)  # shared by every merge — never allocated again
    _sort_range(values, buffer, 0, len(values))


def _sort_range(values: List[int], buffer: List[int], lo: int, hi: int) -> None:
    """Sort values[lo..hi) — lo included, hi excluded."""
    if hi - lo < 2:
        return  # zero or one value: already sorted

    mid = lo + (hi - lo) // 2
    _sort_range(values, buffer, lo, mid)  # left half:  [lo, mid)
    _sort_range(values, buffer, mid, hi)  # right half: [mid, hi)
    _merge_halves(values, buffer, lo, mid, hi)


def _merge_halves(values: List[int], buffer: List[int], lo: int, mid: int, hi: int) -> None:
    """Merge the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi)."""
    for k in range(lo, hi):
        buffer[k] = values[k]  # set both halves aside

    i = lo  # next unused value of the left half
    j = mid  # next unused value of the right half
    k = lo  # next slot to fill in values

    while i < mid and j < hi:
        # <=, not <: on a tie the left value goes first, which is what makes the sort stable.
        if buffer[i] <= buffer[j]:
            values[k] = buffer[i]
            i += 1
        else:
            values[k] = buffer[j]
            j += 1
        k += 1
    while i < mid:
        values[k] = buffer[i]
        i += 1
        k += 1
    # Whatever is left of the right half is already in place: k has caught up with j.

/**
 * Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
 * halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
 */
public final class MergeSort {
    private MergeSort() {
    }

    /**
     * Sorts values in ascending order, in place.
     * Stable: equal values keep the order they started in.
     */
    public static void mergeSort(int[] values) {
        int[] buffer = new int[values.length]; // shared by every merge — never allocated again
        sortRange(values, buffer, 0, values.length);
    }

    /** Sorts values[lo..hi) — lo included, hi excluded. */
    private static void sortRange(int[] values, int[] buffer, int lo, int hi) {
        if (hi - lo < 2) {
            return; // zero or one value: already sorted
        }

        int mid = lo + (hi - lo) / 2;
        sortRange(values, buffer, lo, mid); // left half:  [lo, mid)
        sortRange(values, buffer, mid, hi); // right half: [mid, hi)
        mergeHalves(values, buffer, lo, mid, hi);
    }

    /** Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi). */
    private static void mergeHalves(int[] values, int[] buffer, int lo, int mid, int hi) {
        for (int k = lo; k < hi; k++) {
            buffer[k] = values[k]; // set both halves aside
        }

        int i = lo; // next unused value of the left half
        int j = mid; // next unused value of the right half
        int k = lo; // next slot to fill in values

        while (i < mid && j < hi) {
            // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
            if (buffer[i] <= buffer[j]) {
                values[k++] = buffer[i++];
            } else {
                values[k++] = buffer[j++];
            }
        }
        while (i < mid) {
            values[k++] = buffer[i++];
        }
        // Whatever is left of the right half is already in place: k has caught up with j.
    }
}

// Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
// halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
// (In real code reach for std::stable_sort — a tuned merge sort with the same guarantee.)
#include <vector>

// Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi).
void mergeHalves(std::vector<int>& values, std::vector<int>& buffer, int lo, int mid, int hi) {
    for (int k = lo; k < hi; ++k) {
        buffer[k] = values[k];  // set both halves aside
    }

    int i = lo;   // next unused value of the left half
    int j = mid;  // next unused value of the right half
    int k = lo;   // next slot to fill in values

    while (i < mid && j < hi) {
        // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
        if (buffer[i] <= buffer[j]) {
            values[k++] = buffer[i++];
        } else {
            values[k++] = buffer[j++];
        }
    }
    while (i < mid) {
        values[k++] = buffer[i++];
    }
    // Whatever is left of the right half is already in place: k has caught up with j.
}

// Sorts values[lo..hi) — lo included, hi excluded.
void sortRange(std::vector<int>& values, std::vector<int>& buffer, int lo, int hi) {
    if (hi - lo < 2) {
        return;  // zero or one value: already sorted
    }

    int mid = lo + (hi - lo) / 2;
    sortRange(values, buffer, lo, mid);  // left half:  [lo, mid)
    sortRange(values, buffer, mid, hi);  // right half: [mid, hi)
    mergeHalves(values, buffer, lo, mid, hi);
}

// Sorts values in ascending order, in place.
// Stable: equal values keep the order they started in.
void mergeSort(std::vector<int>& values) {
    std::vector<int> buffer(values.size());  // shared by every merge — never allocated again
    sortRange(values, buffer, 0, static_cast<int>(values.size()));
}