Có hai yếu tố chính khác biệt giữa thuật toán xử lý dữ liệu ngoài với các thuật toán mà chúng ta đã thấy. Trước tiên, chi phí truy xuất một phần tử trong bộ nhớ ngoài thì lớn hơn bất kỳ chi phí tính toán nào. Thứ hai là phải chịu các giới hạn nghiêm ngặt về truy xuất, phụ thuộc vào môi trường lưu trữ bên ngoài: ví dụ như các phần tử lưu trữ trên băng từ chỉ truy xuất theo phương thức tuần tự.

Sự khác biệt lớn của loại và chi phí thiết bị chi phí bên ngoài tạo sự phát triển của các phương pháp sắp xếp bên ngoài rất độc lập về kỹ thuật. Các phương pháp này có thể phức tạp và nhiều tham số ảnh hưởng đến tính năng của chúng: một phương pháp tốt, có thể không được chưng dụng vì chỉ thay đổi chút đỉnh về kỹ thuật mà không có lợi cho sắp xếp ngoài. Vì lý do đó, trong bài viết này chúng ta sẽ tập trung vào các phương pháp tổng quát thay vì chú ý các cài đặt cụ thể.

Tóm lại, đối với sắp xếp ngoài, phương diện "hệ thống" chắc chắn quan trọng như phương diện "thuật toán". Cả hai lĩnh vực nên xem xét kỹ lưỡng một khi cần phát triển phương pháp sắp xếp ngoài cho hiệu quả. Chi phí cơ bản trong việc sắp xếp ngoài là dành cho nhập - xuất. Một bài tập hay dành cho độc giả nào định cài đặt định cài đặt một chương trình hiệu quả để sắp xếp một tập tin có kích thước lớn trước tiên là cài đặt một chương trình hiệu quả để sao chép tập tin này, kế đó là cài đặt một chương trình để đảo ngược thứ tự của các phần tử trong tập tin này. Vấn đề hệ thống nảy sinh khi thử giải quyết các bài toán này tương tự như vấn đề hệ thống nảy sinh khi sắp xếp ngoài. Hoán vị một tập tin có kích thước lớn cũng khó như sắp xếp nó dù cho không cần phải so sánh khoá... Trong sắp xếp ngoài, chúng ta quan tâm chủ yếu đến giới hạn thời gian di chuyển mỗi thành phần dữ liệu giữa môi trường lưu trữ bên ngoài và bộ nhớ, bà bảo đảm là những lần chuyển giao như thế phải thực hiện một cách hiệu quả với khả năng của phần cứng.

Các phương pháp sắp xếp ngoài phát triển thích hợp với các thẻ đục lỗ và băng giấy trước đây, hiện tại là dùng băng từ và đĩa, các kỹ thuật nổi như bộ nhớ nổi và đĩa video. Sự khác nhau chủ yếu giữa các thiết bị là kích thước tương đối và tốc độ lưu trữ có sẵn và kiểu giới hạn truy xuất dữ liệu. Chúng ta sẽ tập trung vào các phương pháp cơ bản để sắp xếp trên băng từ và đĩa bởi vì các thiết bị này tồn tại để sử dụng phổ biến và đáp ứng được hai cơ chế truy xuất khác nhau đặc trưng cho nhiều hệ thống xử lý bên ngoài. Thông thường các hệ máy tính hiện đại có "phân cấp lưu trữ" của bộ nhớ lớn hơn, rẻ hơn, chậm hơn. Nhiều thuật toán mà chúng ta sẽ tìm hiểu có thể áp dụng tốt trong môi trường như thế, nhưng chúng ta sẽ làm việc với độ phân cấp "hai mức" gồm bộ nhớ chính và đĩa hay băng từ.

Sắp xếp trộn

Phần lớn các phương pháp sắp xếp ngoài sử dụng chiến lược tổng quát sau: tạo một lần duyệt trên tệp tin cấn sắp, chia nó thành các khối có kích thước phù hợp với bộ nhớ trong, và sắp xếp các khối này. Sau đó trộn các khối đã sắp này với nhau bằng cách duyệt vài lần trên tập tin, rồi lại tạo các khối sắp lớn hơn cho đến khi sắp xong toàn bộ tập tin. Đa số dữ liệu thường được truy xuất theo kiểu tuần tự, đây là tính chất làm cho phương pháp này thích hợp đối với các thiết bị bên ngoài. Các thuật toán sắp ngoài cố gắng rút ngắn số lần duyệt trên tập tin và giảm chi phí sao cho gần với chi phí của một bản sao chép.

Bởi vì phần lớn chi phí của phương pháp sắp xếp ngoài là dành cho nhập - xuât, nên chúng ta có thể đo lường bằng chi phí của một phương pháp trộn bằng cách đếm số lần đọc hay ghi mỗi từ trong một tập tin (số lần lặp trên toàn bộ dữ liệu). Trong nhiều ứng dụng, các phương pháp mà chúng ta xem xét liên quan đến thứ tự của mười hay ít hơn các bước như thế. Chú ý là chúng ta quan tâm đến các phương pháp loại trừ một bước đơn lẻ. Thời gian thực hiện toàn bộ quá trình sắp xếp có thể đánh giá dễ dàng như thời gian thực hiện của bài tập "sao chép ngược tập tin".

Trộn nhiều đường cân bằng

Chúng ta sẽ cùng nhau khảo sát một ví dụ nhỏ để có thể cùng lần theo từng bước của thủ tục sắp xếp bằng phương pháp trộn đơn giản nhất. Giả sử là chúng ta có các mẩu tin có các khóa A S O R T I N G A N D M E R G I N G E X A M P L E trên một băng chứa dữ liệu nhập, các khoá này được sắp xếp và xuất lên một băng khác. "Băng" hàm ý là chúng ta giới hạn việc đọc các mẩu tin một cách tuần tự: mẩu tin thứ hai không thể được đọc cho đến khi mẩu tin thứ nhất đọc xong... Giả thiết là chúng ta chỉ có đủ chỗ cho 3 mẩu tin trong bộ nhớ và có sẵn nhiều băng từ.



Hình 1 . Trộn ba đường cân bằng: kết quả của bước thứ nhất.

Bước đầu tiên đọc ba mẩu tin một lúc, sắp xếp chúng để trở thành khối ba mẩu tin, và xuất các khối được sắp được sắp. Vì vậy, trước tiên chúng ta đọc A S O và xuất các khối gồm A O S, kế tiếp đọc R T I và xuất khối I R T và cứ tiếp tục như thế. Theo thứ tự của các khối đã trộn trong này, chúng ta nên đặt các khối lên các bảng khác nhau. Nếu chúng ta thực hiện việc trộn 3 đường, thì sử dụng ba băng, gói gọn trong các lần sắp xếp với cấu hình trình bày ở Hình 1.

Bây giờ chúng ta sẽ sắp khối có kích thước ba. Chúng ta đọc mẩu tin đọc mẩu tin đầu tiên của mỗi băng (có đủ bộ nhớ) và lấy một mẩu tin có khoá nhỏ nhất. Kế tiếp đọc mẩu tin kế trên băng này và lấy tiếp một mẩu tin có khó nhỏ nhất. Khi đến cuối khối có ba từ, băng tương ứng sẽ không thao tác nữa cho đến khi xử lý xong các khối của hai băng khác và chín mẩu tin được xuất ra. Sau đó, quá trình được lặp lại để trộn hai hay ba từ trên mỗi băng thành một khối chín từ (xuất trên một băng khác để chuẩn bị cho lần trộn kế tiếp). Tiếp tục bằng cách này, chúng ta có ba khối dài như hình sau:



Hình 2. Trộn ba đường cân bằng; kết quả của bước thứ hai.

Bây giờ ta thêm một bước trộn ba-đường nữa để hoàn tất việc sắp xếp. Nếu chúng ta có một tập tin dài hơn với nhiều khối với kích thước là chín trên mỗi băng, thì chúng ta sẽ hoàn tất bước thứ hai với khối với kích thước là 27 trên băng 1, 2, 3, kế đến bước thứ ba sẽ cho ra khối có kích thước 81 trên băng 4, 5, 6 và cứ thế mà tiếp tục. Chúng ta cần sáu băng để sắp một tập tin lớn tuỳ ý: ba để nhập và ba để xuất cho mỗi lần trộn ba- đường (Thực sự chúng ta chỉ cần bốn băng: có thể chỉ xuất trên một băng, và sau đó các khối từ băng này được phân phối cho các băng giữa và các lần trộn.)

Phương pháp này gọi là Trộn nhiều đường cân bằng: một thuật toán hợp lý để sắp ngoài và cũng là một quan điểm tốt để cài đặt một phương pháp sắp ngoài. Các thuật toán phức tạp hơn nữa (sẽ giới thiệu trong các kỳ sau) có thể tạo đường chạy sắp xếp nhanh hơn chút nữa, nhưng không nhiều lắm. (Tuy nhiên, khi thời gian thực hiện tính bằng đơn vị giờ thì ngay cả giảm bớt một tỉ lệ nhỏ cũng đã rất đáng kể.)

Giả sử chúng ta có N từ thao tác trong quá trình sắp xếp và bộ nhớ trong có kích thước M. Sau đó lần "sắp" cho ra khoảng N/M khối đã sắp (đánh giá này giả thiết trên các mẩu tin 1 từ; đối với mẩu tin lớn hơn: số khối được sắp được tính bằng cách nhân với kích thước mẩu tin). Nếu chúng ta thực hiện trộn P đường trong mỗi bước, thì số lần lặp tính khoảng logP (N/M), bởi vì mỗi bước rút ngắn số khối đã sắp bởi một hệ số P.

Mặc dù với các ví dụ nhỏ có thể giúp chúng ta hiểu chi tiết thuật toán, nhưng tốt nhất là sử dụng các tập tin có kích thước lớn hơn khi làm việc với sắp ngoài. Chẳng hạn, công thức ở trên cho thấy trộn bốn-đường để sắp một tập tin 200- triệu - từ trên máy tính có một triệu từ bộ nhớ thì chỉ cần tổng cộng khoảng năm bước. Một đánh giá khác về thời gian chạy cũng tính được bằng năm lần thời gian thực hiện cho cài đặt của bản sao tập tin theo thứ tự ngược ở trên.