thucnq

Merge sort chia danh sách dữ liệu cần được sắp xếp thành hai nữa bằng nhau, và đặt chúng vào các vùng chứa dữ liệu riêng biệt (list, array,...). Mỗi mảng dữ liệu được sắp xếp một cách đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được sắp xếp cuối cùng. Giống như hầu hết các phương pháp sắp xếp đệ quy, Merge sort có độ phức tạp là O(n log n).


Cách triển khai cơ bản của Merge sort là dùng ba mảng dữ liệu - mỗi mảng để chứa mổi nữa của tập dữ liệu cần sắp xếp và một mảng chứa danh sách được sắp xếp cuối cùng. Thuật toán được giới thiệu sau đây trộn các mảng lại thành một, vì vậy chỉ sử dụng hai mảng cho toàn bộ quá trình xử lý. Hiện nay cũng tồn tại phiên bản không đệ quy của Merge sort, nhưng chúng không thu được bất kì một cải tiến tốc độ nào so với phiên bản đệ quy qua thử nghiệm trên hầu hết các kiến trúc xử lý.

Merge sort thì nhanh hơn một ít so với Heap sort với các tập dữ liệu lớn, nhưng nó đòi hỏi 2 lần bộ nhớ so với Heap sort vì vậy nó không được ưa chuộng trong việc triển khai ứng dụng dù cho mục đích là gì - Quick sort là lựa chọn tốt hơn cho thời gian và Heap sort thì lại là lựa chọn tốt hơn với các tập dữ liệu rất lớn.

Giống như Quick sort, Merge sort là phương pháp dựa trên đệ quy, điều này khiến nó sẽ là lựa chọn tồi với các ứng dụng chạy trên máy tính bị giới hạn về bộ nhớ.

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán Sắp xếp trộn (Merge Sort) http://www.laptrinhviet.com/showthread.php?t=19824 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều