Алгоритми та структури даних · Senior · Запитання 19 з 75
Як відсортувати файл на 200 ГБ на машині з 8 ГБ RAM?
- 1Розбити за першим символом і сортувати кожен файл окремо
- ✓Правильна відповідь: Сортувати частини, що вміщуються в пам'ять, потім k-шляхове злиття з купою
- 3Завантажити його через memory-mapped I/O і викликати звичайне сортування
Пояснення
Зовнішнє сортування злиттям записує відсортовані серії на диск, а потім зливає їх, читаючи кожну серію послідовно. Купа вибирає найменшу голову серед k серій за O(log k). Розбиття за першим символом не вирівнює розміри частин.