Сортировка огромного файла с массивом при известном словаре данных

Привет Хабр! Недавно пришло интересное задание:

Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.

Итак, меня смутил словарь данных: от 1 до 10000 и в то же время ограниченность ресурсов. Решил сделать следующее. Для начала будем генерировать нужный нам входной файл, не руками же его писать. Для этого использовал старый добрый rnd:

System.IO.StreamWriter file = new System.IO.StreamWriter(@"C:\1\Nabor.txt", true); //Создаём файлик
Random rnd = new Random();
this.progressBar1.Maximum = Convert.ToInt32(this.textBox1.Text); //Будет нам показывать процесс записи
int value;
for (int i = 0;i<Convert.ToInt32(this.textBox1.Text);i++) //шуруем циклом по заданному колличеству
{
      value = rnd.Next(0, 10000);
      file.WriteLine(value);      //Собственно генерация и запись в наш файл
      this.progressBar1.Value++;
}
file.Close();

Далее сама сортировка:

1. Создаём массив int[10000]. В ОЗУ это займёт 40 Мб. На C# (на других языках чуть больше). Я буду называть его массивRAM, массив исходный — массивIN, и массив выходной — МассивOUT.

Почему 10000? Потому что словарь данных у нас в диапазоне от 1 до 10000.

2. Читаем исходный файл поэлементно ( в моём случае построчно) и делаем следующее с каждой записью:

string line; //Объявляем строку как читаемый элемент
int[] arr;
arr = new int[10000]; //Объявляем наш массив
System.IO.StreamReader file2 = new System.IO.StreamReader(@"C:\1\Nabor.txt");
while ((line = file2.ReadLine()) != null)
{
       arr[Convert.ToInt32(line)]++; // плюсуем одно повторение для элемента
}
file2.Close();

То есть в элемент массиваRAM с индексом, равному считанному значению из массиваIN делаем +1. В итоге в массивеRAM будет содержаться количество повторений каждого элемента из массиваIN.

Наглядно постарался изобразить на рисунке:

3. И последним этапом мы пробегаем по нашему массивуRAM и записываем поочерёдно все индексы элементов массиваRAM по количеству их повторений:

System.IO.StreamWriter file3 = new System.IO.StreamWriter(@"C:\1\Sort.txt", true);
int i, j;
for (i=0;i<10000;i++)
      {
      if (arr[i]>0) // Если вообще элемент встречался
              {
              for (j = 0; j < arr[i]; j++) // Цикл, сколько раз встречался = значение нашего массиваRAM
                    {
                        file3.WriteLine(i); //Записываем индекс нашего массива, а не его значение
                    }
              }
      }
file3.Close();

Таким образом файл размером 575Мб с 100 000 000 записями был отсортирован и записан за 7,53 секунд на машине: AMD A10, 6Гб, SATA. Без жадности к памяти и ресурсам.

Напоследок хочу сказать, что использовать данный метод нужно осторожно, избегая переполнения типов. То есть, если взять массив из 5 000 000 000 значений пусть с тем же словарём данных, и предположить, что все значения в нём будут одно и тоже число, то совершится переполнение типа int, и программа выдаст исключение.

Весь проект, думаю, выкладывать смысла нет, но если будут пожелания, то выложу. Удачных разработок!)