Tôi chưa thể tìm thấy bất kỳ cuộc thảo luận nào nói rằng một phương pháp hợp nhất phải nhanh hơn phương pháp kia.
Các loại hợp nhất từ trên xuống và dưới cùng, cũng như các biến thể khác, đã được nghiên cứu kỹ trong suốt những năm 90. Tóm lại, nếu bạn đo chi phí như số so sánh của các khóa riêng lẻ, chi phí tốt nhất là như nhau (~ (n lg n)/2), chi phí thấp nhất từ trên xuống thấp hơn hoặc bằng mức thấp nhất trường hợp từ dưới lên (nhưng cả hai ~ n lg n) và chi phí trung bình từ trên xuống thấp hơn hoặc bằng với trường hợp trung bình từ dưới lên (nhưng cả hai ~ n lg n), trong đó "lg n" là logarit nhị phân. Sự khác biệt xuất phát từ các thuật ngữ tuyến tính. Tất nhiên, nếu n = 2^p, hai biến thể trên thực tế là giống nhau. Điều này có nghĩa là, so sánh-khôn ngoan, từ trên xuống luôn luôn tốt hơn so với từ dưới lên. Hơn nữa, nó đã được chứng minh rằng chiến lược phân chia "nửa rưỡi" của loại hợp nhất từ trên xuống là tối ưu. Các tài liệu nghiên cứu từ Flajolet, Golin, Panny, Prodinger, Chen, Hwang và Sedgewick.
Dưới đây là những gì tôi đã đưa ra trong cuốn sách Thiết kế và Phân tích của tôi về chương trình thuần túy chức năng (Cao đẳng Publications, Vương quốc Anh), trong Erlang:
tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T) -> T.
cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S, T, U) -> mrg(tms(S),tms(T)).
mrg( [], T) -> T;
mrg( S, []) -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg( [X|S], T) -> [X|mrg(S,T)].
Lưu ý rằng đây là không một loại ổn định. Ngoài ra, trong Erlang (và OCaml), bạn cần sử dụng bí danh (ALIAS = ...) trong các mẫu nếu bạn muốn lưu bộ nhớ. Bí quyết ở đây là tìm ra giữa danh sách mà không biết chiều dài của nó. Điều này được thực hiện bởi cutr/3 xử lý hai con trỏ đến danh sách đầu vào: một con trỏ được tăng lên một và cái còn lại là hai, vì vậy khi con trỏ đến cuối, cái đầu tiên nằm ở giữa. (Tôi đã học được điều này từ một bài báo của Olivier Danvy.) Bằng cách này, bạn không cần phải theo dõi độ dài và bạn không sao chép các ô của nửa sau của danh sách, vì vậy bạn chỉ cần (1/2) n lg n không gian thừa, so với n lg n . Đây không phải là nổi tiếng.
Người ta thường cho rằng biến thể từ dưới lên thích hợp hơn cho các ngôn ngữ chức năng hoặc danh sách liên kết (Knuth, Panny, Prodinger), nhưng tôi không nghĩ điều này là đúng.
Tôi đã bối rối như bạn bởi việc thiếu thảo luận về các loại hợp nhất, vì vậy tôi đã nghiên cứu riêng của mình và viết một chương lớn về nó. Tôi hiện đang chuẩn bị một ấn bản mới với nhiều tài liệu hơn về các loại hợp nhất.
Nhân tiện, có các biến thể khác: sắp xếp hợp nhất hàng đợi và sắp xếp hợp nhất trực tuyến (tôi thảo luận về sau trong sách của tôi).
[EDIT: Do số đo cho chi phí là số so sánh, không có sự khác biệt giữa việc chọn một mảng so với danh sách được liên kết. Tất nhiên, nếu bạn thực hiện biến thể từ trên xuống với danh sách được liên kết, bạn phải thông minh, vì bạn không nhất thiết phải biết số lượng khóa, nhưng bạn sẽ cần phải đi qua ít nhất một nửa khóa, mỗi lần và tái phân bổ, trong tổng số (1/2) n lg n tế bào (nếu bạn thông minh). Sắp xếp hợp nhất từ dưới lên với danh sách được liên kết thực sự yêu cầu nhiều bộ nhớ bổ sung hơn, n lg n + n ô. Vì vậy, ngay cả với danh sách được liên kết, biến thể từ trên xuống cũng là lựa chọn tốt nhất. Theo như độ dài của chương trình đi, mileage của bạn có thể khác nhau, nhưng trong một ngôn ngữ chức năng, sắp xếp hợp nhất từ trên xuống có thể được thực hiện ngắn hơn từ dưới lên, nếu sự ổn định là không cần thiết. Có một số giấy tờ thảo luận về các vấn đề triển khai sắp xếp hợp nhất, như tại chỗ (mà bạn cần mảng), hoặc độ ổn định vv. Ví dụ: Phân tích tỉ mỉ các chương trình hợp nhất, bởi Katajainen và Larsson Traff (1997).]
Các so sánh và trao đổi là các chi phí chính trong phân tích sắp xếp, tôi khá chắc chắn. – Pointy
@Pointy có, thông thường họ sẽ là các mục để phân tích khi so sánh các thuật toán sắp xếp khác nhau. Nhưng trong trường hợp này, chúng phải giống nhau ... chúng là cùng một thuật toán, vì vậy đó không phải là những gì tôi theo sau. Thực hiện của tôi phản ánh những gì có trong cuốn sách ... là nó chỉ có thể là từ dưới lên sử dụng ít vòng hơn/thông qua mảng nhưng có cùng số lượng so sánh/di chuyển? – arthurakay
@NiklasB. Tôi thấy quan điểm của bạn ... nhưng những người đó không góp phần vào sự chênh lệch trong số lần lặp lại của tôi. Nếu bạn nhìn vào mã của tôi, tôi chỉ theo dõi các lần lặp trong vòng lặp đệ quy/lặp lại. Math.floor() không liên quan gì đến nó - Tôi không sử dụng phân tích dựa trên thời gian – arthurakay