O(n log n)

O(n log n): Linearithmic Time

Đặc điểm

• Thường thấy trong các thuật toán sắp xếp hiệu quả
• Hiệu suất tốt cho dữ liệu lớn
• Tối ưu hơn nhiều so với O(n²)

Ví dụ: Merge Sort

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));    // Đệ quy nửa trái
    const right = mergeSort(arr.slice(mid));      // Đệ quy nửa phải

    return merge(left, right);                    // Trộn hai nửa
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i), right.slice(j));
}

Minh họa Merge Sort

Ví dụ sắp xếp mảng: [38, 27, 43, 3, 9, 82, 10]

Bước 1: Chia đôi liên tục
[38, 27, 43, 3, 9, 82, 10]
       ↓
[38, 27, 43, 3]    [9, 82, 10]
       ↓                ↓
[38, 27] [43, 3]    [9, 82] [10]
    ↓       ↓         ↓
[38] [27] [43] [3]  [9] [82] [10]

Bước 2: Trộn từ dưới lên
[27, 38] [3, 43]    [9, 82] [10]
       ↓                ↓
[3, 27, 38, 43]    [9, 10, 82]
            ↓
[3, 9, 10, 27, 38, 43, 82]

Tại sao O(n log n)?

• Chia đôi: log n cấp độ (chiều sâu cây)
• Trộn: n phép so sánh mỗi cấp độ
• Tổng: n × log n
• Ví dụ trực quan: O(n log n)