Сортировка с небольшим объемом памяти

Question

Каков наилучший способ сортировки словаря размером 1 ГБ (255 символов для каждого слова) с 2 ГБ ОЗУ?Я уже попробовал быструю сортировку и не получил приемлемый результат.Код быстрой сортировки:

#include <iostream>
#include <fstream>
#include <cstring>

#define MAXL 4000000
using namespace std;
void swap(char *&ch1,char *&ch2)
{
    char *temp = ch1;
    ch1 = ch2;
    ch2 = temp;
}

int partition (char **arr, int low, int high)
{
    string pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(char **arr, int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


int main()
{
    fstream file("input.txt",ios::in|ios::out|ios::app);
    fstream o("output.txt",ios::out);

    char **arr = new char*[MAXL];
    for(int i=0;i<MAXL;i++)
        arr[i] = new char[255];

    long long i=0;
    while(file)
    {
//words are sepearated by spcae
        file.getline(arr[i],256,' ');
        i++;
    }

    file.close();
    quickSort(arr, 0, i-2);

    for(long long j=0;j<i-1;j++)
    {
        o << arr[j] << "\n";
    }
}

. Для сортировки упомянутого списка требуется более 10 минут, но не более 20 секунд.(MAXL - количество слов в файле 1G, а входные слова хранятся в текстовом файле)

Answer 1

Если вы не можете поместить все это в память, сортировка слиянием на основе файлов будет работать хорошо.

Answer 2

Алгоритмы на месте - это ваше решение.Найти больше здесь :

В качестве другого примера, многие алгоритмы сортировки переставляют массивы в отсортированный порядок на месте, включая пузырьковую сортировку, гребенную сортировку, выборочную сортировку, вставку, сортировку, heapsort,и Shell вроде.Эти алгоритмы требуют только нескольких указателей, поэтому их сложность составляет O (log n).