Sắp xếp trộn (Merge Sort): giải thích dễ hiểu, đếm nghịch thế, code C++ và Python

#include <iostream>
#include <vector>
using namespace std;

// Trộn hai đoạn đã tăng dần a[lo .. mid] và a[mid + 1 .. hi]
void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> trai(a.begin() + lo, a.begin() + mid + 1);
    vector<int> phai(a.begin() + mid + 1, a.begin() + hi + 1);

    size_t i = 0, j = 0;
    int k = lo;

    while (i < trai.size() && j < phai.size()) {
        // Dùng dấu <= để giữ nguyên thứ tự các phần tử bằng nhau (Stable Sort)
        if (trai[i] <= phai[j]) {
            a[k++] = trai[i++];
        } else {
            a[k++] = phai[j++];
        }
    }
    while (i < trai.size()) a[k++] = trai[i++];
    while (j < phai.size()) a[k++] = phai[j++];
}

// Sắp xếp trộn (Merge Sort) trên đoạn a[lo .. hi]
void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

void inMang(const vector<int>& a) {
    for (size_t i = 0; i < a.size(); i++) {
        cout << a[i] << (i + 1 == a.size() ? "\n" : " ");
    }
}

int main() {
    vector<int> a1 = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(a1, 0, (int)a1.size() - 1);
    inMang(a1);  // 3 9 10 27 38 43 82

    vector<int> a2 = {5, -2, 0, 5, -2, 1};
    mergeSort(a2, 0, (int)a2.size() - 1);
    inMang(a2);  // -2 -2 0 1 5 5

    vector<int> a3 = {100};
    mergeSort(a3, 0, (int)a3.size() - 1);
    inMang(a3);  // 100
    return 0;
}

def merge(trai, phai):
    """Trộn hai danh sách đã tăng dần thành một danh sách tăng dần (ổn định)."""
    ket_qua = []
    i, j = 0, 0
    while i < len(trai) and j < len(phai):
        if trai[i] <= phai[j]:  # dùng <= để bảo toàn tính ổn định (stable)
            ket_qua.append(trai[i])
            i += 1
        else:
            ket_qua.append(phai[j])
            j += 1
    ket_qua.extend(trai[i:])
    ket_qua.extend(phai[j:])
    return ket_qua


def merge_sort(a):
    """Sắp xếp trộn (Merge Sort) trả về danh sách mới đã sắp xếp tăng dần."""
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    nua_trai = merge_sort(a[:mid])
    nua_phai = merge_sort(a[mid:])
    return merge(nua_trai, nua_phai)


for arr in ([38, 27, 43, 3, 9, 82, 10], [5, -2, 0, 5, -2, 1], [100]):
    print(*merge_sort(arr))

#include <iostream>
#include <vector>
using namespace std;

// Vừa sắp xếp đoạn a[lo .. hi] vừa trả về số cặp nghịch thế trong đoạn đó
long long demNghichThe(vector<int>& a, vector<int>& tam, int lo, int hi) {
    if (lo >= hi) return 0;

    int mid = lo + (hi - lo) / 2;
    long long dem = 0;
    dem += demNghichThe(a, tam, lo, mid);
    dem += demNghichThe(a, tam, mid + 1, hi);

    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            tam[k++] = a[i++];
        } else {
            // Vì a[lo .. mid] đã tăng dần, mọi phần tử từ a[i] đến a[mid] đều > a[j]
            dem += (mid - i + 1);
            tam[k++] = a[j++];
        }
    }
    while (i <= mid) tam[k++] = a[i++];
    while (j <= hi) tam[k++] = a[j++];
    for (int p = lo; p <= hi; p++) a[p] = tam[p];

    return dem;
}

long long soCapNghichThe(vector<int> a) {
    if (a.empty()) return 0;
    vector<int> tam(a.size());
    return demNghichThe(a, tam, 0, (int)a.size() - 1);
}

int main() {
    cout << soCapNghichThe({38, 27, 43, 3, 9, 82, 10}) << "\n";  // 11
    cout << soCapNghichThe({2, 4, 1, 3, 5}) << "\n";             // 3
    cout << soCapNghichThe({5, 4, 3, 2, 1}) << "\n";             // 10
    return 0;
}

def so_cap_nghich_the(arr):
    """Đếm số cặp nghịch thế (i < j mà arr[i] > arr[j]) trong O(n log n) bằng Merge Sort."""
    a = arr[:]
    tam = [0] * len(a)

    def _dem(lo, hi):
        if lo >= hi:
            return 0
        mid = (lo + hi) // 2
        dem = _dem(lo, mid) + _dem(mid + 1, hi)

        i, j, k = lo, mid + 1, lo
        while i <= mid and j <= hi:
            if a[i] <= a[j]:
                tam[k] = a[i]
                i += 1
            else:
                # Mọi phần tử từ a[i] đến a[mid] đều lớn hơn a[j]
                dem += mid - i + 1
                tam[k] = a[j]
                j += 1
            k += 1

        while i <= mid:
            tam[k] = a[i]
            i += 1
            k += 1
        while j <= hi:
            tam[k] = a[j]
            j += 1
            k += 1
        a[lo : hi + 1] = tam[lo : hi + 1]
        return dem

    return _dem(0, len(a) - 1) if a else 0


print(so_cap_nghich_the([38, 27, 43, 3, 9, 82, 10]))  # 11
print(so_cap_nghich_the([2, 4, 1, 3, 5]))             # 3
print(so_cap_nghich_the([5, 4, 3, 2, 1]))             # 10