Trong tài liệu này các bạn sẽ tìm hiểu về thuật toán Merge sort một thuật toán theo tư tưởng chộn để cho ra kết quả đã sắp xếp. Theo phương pháp đệ quy | HOA SEN UNIVERSITY Merge sort trực tiếp bước túcha thành b c 00000000 0 0 0 0 0 0 0 0 41 HOA SEN UNIVERSITY Merge sort trực tiếp Đánh giá thuật toán - Chi phí thực hiện MergeSort là O nlgn - Nhược điểm Không tận dụng được đặc tính của dãy cần sắp xếp. Ví dụ Trường hợp dãy đã có sẵn thứ tự - - Thuật toán Merge sort cải tiến Phương pháp trộn tự nhiên Natural Merge sort 42 UNIVERSITY Natural Merge sort Khái niệm đường chạy run Một đường chạy của dãy a là 1 dãy con không giảm của a. Nghĩa là đường chạy r a ai 1 . aj phải thỏa điều Ví du Cho dãy a 12 2 8 5 1 6 4 15 có 5 đường chạy gồm 12 2 8 5 1 6 4 15
