Massive file sorting algorithm I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, sort them using one of classic sort algorithms, write them to a new file, then repeat the process and merge the two files and so on. You can find more here

I tried to make a new algorithm that does not require a lot of memory. I ended up with this code that actually works and is inspired from Bubble sort algorithm:

#include&lt;stdio.h&gt;
int main()
{
char a,b;
FILE *f,*aux;

int sorted;//BOOLEAN
do
{        
    f = fopen("ltr.txt","r"); //Assuming that the file exists
    aux = fopen("aux.txt","w+");
    a = getc(f);
    sorted = 1;
    while ( (b = getc(f)) != EOF )
    {
        if (b &lt; a)  
        {
            fputc(b, aux);
            sorted = 0;
        }
        else
        {
            fputc(a, aux);
            a = b;
        }
    }
    fputc(a, aux);
    fclose(f);
    fclose(aux);
    remove("ltr.txt");
    rename("aux.txt","ltr.txt");
}while(!sorted);
return 0; //EXIT_SUCCESS
}


The algorithm works but is improvable and can be optimized, however I'm asking for help by reviewing complexity, performance, read/write to disk, disk management, memory management and comparison to other sorting algorithms.

I can list some disadvantages: 


requires disk space of file_size*2 (can be improved by deleting original char each time we write it to aux.txt)
file will be written to disk several times and the original will be deleted
execution time looks to be too long (yet I didn't measure it)
If you are certain that you only have standard ASCII characters in the file, it's more efficient to just map the whole space and print it out with a counting sort.

The idea is that you use the character itself (a number between 0 and 255) as the index of an array, count how many of those are in the file, and then write the array starting from the beginning.

This is some sample code. Please note that I cannot test it right now, but it should give you a basic idea on how to do it.

#include &lt;stdio.h&gt;

int main()
{
    //You may want to consider a 'long long' type
    long char_count[256];

    FILE *input_file, *output_file;

    input_file = fopen("ltr.txt","r"); //Assuming that the file exists
    output_file = fopen("aux.txt","w+");
    memset(char_count, -1, 256);
    char input_char;
    while (input_char = getc(input_file)) {
        char_count[input_char] = char_count[input_char] &gt; 0 ? (char_count[input_char] + 1) : 1;
    }

    int index;
    for (index = 0; index &lt; 255; index++) {
        if (char_count[input_char] &gt; 0) {
            int char_index;
            //Can be optimized by building a format string and using fprintf
            for (char_index = 0; char_index &lt; char_count[input_char]; char_index++) {
                fputc(char_count[input_char], output_file);
            }
        }
    }
    fclose(output_file);
    fclose(input_file);

    return 0;
}