Đây là câu hỏi phỏng vấn Google: Cho 2 máy, mỗi máy có RAM 64 GB, chứa tất cả các số nguyên (8 byte), sắp xếp toàn bộ dữ liệu 128 GB. Bạn có thể giả sử một lượng nhỏ RAM bổ sung. Mở rộng nó để sắp xếp dữ liệu được lưu trữ trong 1000 máy.

Tôi nghĩ đến việc sắp xếp bên ngoài. Bởi vì chúng tôi chia toàn bộ dữ liệu thành các khối và sử dụng phương pháp sắp xếp hợp nhất trên chúng. Đây là việc sắp xếp các khối lần đầu tiên, sau đó đặt chúng trở lại, sau đó ghép chúng lại thành từng mảnh và hợp nhất chúng. Có cách nào tốt hơn? Nó phức tạp đến mức nào?

câu trả lời hay nhất

ChingPing khuyến nghị sắp xếp O(n log n) của từng tập hợp con, sau đó là hợp nhất tuyến tính (bằng cách hoán đổi các phần tử). Vấn đề với Quicksort (và hầu hết các loại n log n) là chúng yêu cầu n bộ nhớ. Tôi khuyên bạn nên sử dụng thay thế Sắp xếp mượt mà, sử dụng bộ nhớ không đổi và vẫn chạy ở O(n log n).

Trường hợp xấu nhất là bạn có một cái gì đó như thế này:

setA = [maxInt.. 1]
setB = [0..minInt]

Thứ tự của hai bộ bị đảo ngược, nhưng thứ tự hợp nhất bị đảo ngược.

Giải thích (IMO - rõ ràng hơn) về giải pháp của ChingPing là:

Có một con trỏ 'pointerA', 'pointerB' được khởi tạo ở đầu mỗi mảng
Trong khi con trỏ của setA không ở cuối
  if (setA[con trỏA] < setB[con trỏB])
    thì { con trỏA++ }
    khác { trao đổi (setA [con trỏA], setB [con trỏB]); con trỏB++ }

Cả hai bộ sưu tập bây giờ sẽ được sắp xếp.

Về thuật toán - sắp xếp dữ liệu lớn hơn kích thước RAM, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/8584779/