2
\$\begingroup\$

For comparison with other external sorting algorithms, I have implemented external polyphase merge sort, purported to be useful to sort large files that do not fit into main memory. More theoretical info about the algorithm itself can be found here.
My implementation uses a Priority Queue (PQ) as the internal data structure used to extract the smallest element when needed. Elements of the PQ are of a type StringRecord which represents a single line from the main input file.

The algorithm works as expected but it is very slow.
The first - distribution phase works just fine without any performance issues.
The problem must be somewhere in the second - merge phase. I have already removed/fixed some minor performance issues but the major issue is obviously still present.
For benchmarking, this ~786 MB input file with 134217728 lines has been generated. In one test with all files on a local WD Blue 1 TB HDD with 16 MB of cache, sorting took about 230 seconds after warm-up. Timing has been established using System.currentTimeMillis() & System.out.println() as shown.

/**
* StringRecord class represent a single line of text in input files that algorithm is working with
* in merge procedure. It is defined by two attributes: value itself and a file index where value is stored in.
*/
public class StringRecord implements Comparable<StringRecord>
{
    /** String value of this StringRecord. */
    private String value;

    /** Index of an input file where this value is stored in. */
    private int file_index;

    /**
    * Constructor used to create new instance of StringRecord class.
    * 
    * @param value      string value of this StringRecord.
    * @param file_index index of a file where @param value is stored in.
    */
    public StringRecord(String value, int file_index)
    {
        this.value = value;
        this.file_index = file_index;
    }

    /**
    * Returns value of this StringRecord object.
    */
    public String getValue()
    {
        return value;
    }

    /**
    * Returns file_index of this StringRecord object.
    */
    public int getFileIndex()
    {
        return file_index;
    }

    /**
    * Compares this StringRecord value to @param string_record value for their lexicographical order.
    *
    * It returns 0 if the argument is a string value lexicographically equal to this string value,
    * less than 0 if the argument is a string value lexicographically greater than
    * this string value and greater than 0 if the argument is a string value lexicographically
    * less than this string value.
    * 
    * @param string_record string record where it's value is compared to this object value.
    */
    public int compareTo(StringRecord string_record)
    {       
        return this.value.compareTo(string_record.value);
    }
}

import java.io.*;
import java.util.PriorityQueue;

/**
* PMSS algorithm sorts input text file of strings using polyphase merge procedure with a help of two or more auxilary files.
* In the first part it uses these files to distribute input data and then merges them in the second part.
* <p>
* Distribution of the input data is based on Fibonacci numbers sequence which is depending
* on number of auxilary files that algorithm is working with. The algorithm uses internal
* data structure <i>PriorityQueue</i> to store run elements. Priority queue is also used
* to find a minimum element that will be first written to the output file.
* The algorithm uses a class named <i>StringRecord</i> which represent a single line in
* input file defined by two attributes: value itself and file index where value is stored in.
* All elements of the priority queue are of type StringRecord.
* <p>
* Distribute procedure repeats until entire input data is distributed following Fibonacchi sequence numbers.
* Merge procedure repeats until all the data is sorted in ascending order. The algorithm
* produces a brand new output file which contains sorted data and thus retains input file unchanged.
* <p>
* @param temp_files         number of auxiliary files used for data distribution and merging.
* @param working_dir        path to local directory where all the sorting takes place.
* @param main_string_file   local text file which contains all input data separated by new a line character.
*
* @throws IOException       if an input or output exception occurred during file operations.
*
*/
public class PMSS
{
    /** Amount of input data read by input file reader in distribute phase of the algorithm. */
    static long data_read = 0;

    /** Variable used to store the first element of next run. Used only in writeNextStringRun() method. */
    static String next_run_element;

    /** Index of current active output file where runs are being merged. */
    static int output_file_index;

    /** Index of previous active output file (previous distribution level). */
    static int old_output_file_index;

    /** Amount of runs on current distribution level. */
    static int runs_per_level;

    /** Array used to store missing (dummy) runs for each input file after the distribute phase. */
    static int missing_runs[];

    /** Array used to determine distribution of runs in input files. Each input file should
    * contain exactly the same amount of runs as specified in this arrays indexes.
    **/
    static int distribution_array[];    

    /** Array used as a semaphore for input file readers. If value on a certain index equals 1,
    * input file reader is allowed to read from attached file. If value is 0, reading is not allowed.
    **/
    static int allow_read[];

    /** Array used to store all last elements of the current runs from each input file. */
    static String last_elements[];

    /** Array used to store all last elements of the current runs from each input file. Used only in
    * distribute phase of the algorithm.
    **/
    static String run_last_elements[];

    /** Array used to store all first elements of the next runs from each input file. */
    static StringRecord next_run_first_elements[];

    /** 
    * Main data structure of the algorithm. It is used to extract next minimum string
    * that needs to be written to output file. When q is empty on a certain distribution
    * level, all runs on this level have merged to output file.
    */
    static PriorityQueue<StringRecord> q = new PriorityQueue<StringRecord>();

    public static void main(String args[]) throws Exception
    {
        int temp_files = 24;
        String file_extension = ".txt";
        String working_dir = "/path/to/working/directory";
        File main_file = new File(working_dir + "/main" + file_extension);
        File sorted_file = new File(working_dir + "/sorted" + file_extension);
        BufferedReader main_file_reader = new BufferedReader(new FileReader(main_file));
        long main_file_length = main_file.length();

        File working_files[] = new File[temp_files + 1];

        sorted_file.delete();

        allow_read = new int[temp_files + 1];
        missing_runs = new int[temp_files + 1];
        last_elements = new String[temp_files + 1];
        distribution_array = new int[temp_files + 1];
        run_last_elements = new String[temp_files + 1];
        next_run_first_elements = new StringRecord[temp_files + 1];

        String working_file_name = "working_file_";
        BufferedReader run_file_readers[] = new BufferedReader[temp_files + 1];

        for(int i=0; i<working_files.length; i++)
        {
            working_files[i] = new File(working_dir + working_file_name + (i+1) + file_extension);
        }

        /* START - initial run distribution */

        distribute(temp_files, working_files, main_file_length, main_file_reader);

        /* END - initial run distribution */

        /* START - polyphase merge */

        long start = System.currentTimeMillis();

        int min_dummy_values = getMinDummyValue();
        initMergeProcedure(min_dummy_values);
        BufferedWriter writer = new BufferedWriter(new FileWriter(working_files[output_file_index]));

        for(int i=0; i<run_file_readers.length-1; i++)
        {
            run_file_readers[i] = new BufferedReader(new FileReader(working_files[i]));
        }

        while(runs_per_level > 1)
        {
            last_elements[output_file_index] = null;
            merge(distribution_array[getMinFileIndex()] - min_dummy_values, run_file_readers, writer);

            setPreviousRunDistributionLevel();
            updateOutputFileIndex();
            resetAllowReadArray();

            min_dummy_values = getMinDummyValue();
            writer = new BufferedWriter(new FileWriter(working_files[output_file_index]));
            run_file_readers[old_output_file_index] = new BufferedReader(new FileReader(working_files[old_output_file_index]));
        }

        writer.close();
        main_file_reader.close();
        closeReaders(run_file_readers);
        clearTempFiles(working_dir, main_file, working_files);

        long end = System.currentTimeMillis();
        /* END - polyphase merge */

        System.out.println("Merge phase done in " + (end-start) + " ms");
    }

    /**
    * Distributes contents of main input file to @temp_files temporary output files.
    * Input data is distributed according to distribution_array which contains for
    * every temporary file a predifined amount of runs that should reside in certain file
    * on a certain distribution level. Calculation of array values is based on Fibonacci
    * sequence numbers. When input data on a certain level is distributed, next level is calculated
    * if and only if the input file is not consumed yet.
    * 
    * @param temp_files       number of temporary files to work with.
    * @param working_files    array of all working files. The size of this array equals @temp_files.
    * @param main_file_length length of the main input file.
    * @param main_file_reader reader used to read main input file.
    */
    private static void distribute(int temp_files, File working_files[], long main_file_length, BufferedReader main_file_reader)
    {
        try
        {
            long start = System.currentTimeMillis();

            runs_per_level = 1;
            distribution_array[0] = 1;
            output_file_index = working_files.length - 1;

            int write_sentinel[] = new int[temp_files];
            BufferedWriter run_file_writers[] = new BufferedWriter[temp_files];

            for(int i=0; i<temp_files; i++)
            {
                run_file_writers[i] = new BufferedWriter(new FileWriter(working_files[i],true));
            }

            /* START - distribute runs */
            while(data_read < main_file_length)
            {
                for(int i=0; i<temp_files; i++)
                {
                    while(write_sentinel[i] != distribution_array[i])
                    {
                        while(runsMerged(main_file_length, i, next_run_element))
                        {
                            writeNextStringRun(main_file_length, main_file_reader, run_file_writers[i], i);
                        }

                        writeNextStringRun(main_file_length, main_file_reader, run_file_writers[i], i);
                        missing_runs[i]++;
                        write_sentinel[i]++;
                    }
                }
                setNextDistributionLevel();
            }

            closeWriters(run_file_writers);

            setPreviousRunDistributionLevel();
            setMissingRunsArray();

            long end = System.currentTimeMillis();
            System.out.println("Distribute phase done in " + (end-start) + " ms");

            /* END - distribute runs */
        }

        catch(Exception e)
        {
            System.out.println("Exception thrown in distribute(): " + e.getMessage());
        }
    }

    /**
    * Merges predefined amount of dummy runs from all input files to output file.
    * Amount of dummy runs that can be merged is defined by @param min_dummy.
    * Since there should be no special markers in input files, all the merging results
    * as adequate substraction/addition in missing_runs array.
    * Additionaly this method resets allow_read array once dummy run merge is over.
    *
    * @param min_dummy minimum amount of runs which is the same for all input files.
    */
    private static void initMergeProcedure(int min_dummy)
    {
        try
        {
            for(int i=0; i<missing_runs.length - 1; i++)
            {
                missing_runs[i] -= min_dummy;
            }

            missing_runs[output_file_index] += min_dummy;

            resetAllowReadArray();
        }

        catch(Exception e)
        {
            System.out.println("Exception thrown in initMergeProcedure(): " + e.getMessage());
        }
    }

    /**
    * Merges @param min_file_values runs into a single run and writes it to output file bounded by @param writer.
    * @param min_file_values is a minimum number of runs per current distribution level. Procedure merges @param min_file_values
    * from all of the input files and terminates afterwards.
    *
    * @param min_file_values  number of runs that will be merged in a single execution of merge procedure.
    * @param run_file_readers array of all input file readers.
    * @param writer           writer for output file.
    */
    private static void merge(int min_file_values, BufferedReader run_file_readers[], BufferedWriter writer)
    {
        String line;
        int min_file;
        int heap_empty = 0;
        StringRecord record;

        /* Initial heap population */
        populateHeap(run_file_readers);

        try
        {
            while(heap_empty != min_file_values)
            {
                record = q.poll();
                writer.write(record.getValue() + "\n");
                min_file = record.getFileIndex();

                if(allow_read[min_file] == 1 && (line = readFileLine(run_file_readers[min_file],min_file)) != null)
                {
                    q.add(new StringRecord(line,min_file));
                }

                try
                {
                    /* Once heap is empty all n-th runs have merged */
                    if(q.size() == 0)
                    {
                        heap_empty++;

                        for(int i=0; i<next_run_first_elements.length; i++)
                        {
                            try
                            {
                                q.add(new StringRecord(next_run_first_elements[i].getValue(),i));
                                last_elements[i] = next_run_first_elements[i].getValue();
                            }
                            catch(Exception e){}
                        }

                        populateHeap(run_file_readers);
                        resetAllowReadArray();

                        if(heap_empty == min_file_values)
                        {
                            writer.close();
                            return;
                        }
                    }
                }
                catch(Exception e){}
            }
        }
        catch(Exception e)
        {
            System.out.println("Exception thrown in merge(): " + e.getMessage());
        }
    }

    /**
    * Updates current output_file_index which points to output file where runs are being merged to.
    */
    private static void updateOutputFileIndex()
    {
        if(output_file_index > 0)
        {
            output_file_index--;
        }
        else
        {
            output_file_index = distribution_array.length - 1;
        }
    }

    /**
    * Reads next value of each run into a priority queue. Reading is allowed if certain input file
    * contains no dummy runs and reading from input file is allowed by allow_read array.
    *
    * @param run_file_readers array of all input file readers.
    */
    private static void populateHeap(BufferedReader run_file_readers[])
    {
        try
        {
            String line;

            for(int i=0;i<run_file_readers.length;i++)
            {
                if(missing_runs[i] == 0)
                {
                    if((allow_read[i] == 1) && (line = readFileLine(run_file_readers[i],i)) != null)
                    {
                        q.add(new StringRecord(line,i));
                    }
                }

                else
                {
                    missing_runs[i]--;
                }
            }
        }
        catch(Exception e)
        {
            System.out.println("Exception thrown while initial heap population: " + e.getMessage());
        }
    }

    /**
    * Reads next line of text from file bounded by @param file_reader.
    * 
    * @param file_reader reader used to read from input file.
    * @param file_index  index of a file from which @param file_reader reads the data.
    * @return next line of text from file, null instead.
    */
    private static String readFileLine(BufferedReader file_reader, int file_index)
    {
        try
        {
            String current_line = file_reader.readLine();

            /* End of run */
            if(last_elements[file_index] != null && current_line.compareTo(last_elements[file_index]) < 0)
            {               
                next_run_first_elements[file_index] = new StringRecord(current_line,file_index);
                allow_read[file_index] = 0;

                return null;
            }

            else
            {
                last_elements[file_index] = current_line;
                return current_line;
            }
        }
        catch(Exception e)
        {
            allow_read[file_index] = 0;
            next_run_first_elements[file_index] = null;
        }

        return null;
    }

    /**
    * Resets allow_read array to its initial state. It additionally sets
    * index of output_file_index to 0 and thus prevents read operations
    * from output file.
    */
    private static void resetAllowReadArray()
    {
        for(int i=0; i<allow_read.length; i++)
        {
            allow_read[i] = 1;
        }

        allow_read[output_file_index] = 0;
    }

    /**
    * Returns the minimum amount of dummy runs present amongst input files.
    *
    * @return the minimum amount of present runs.
    */
    private static int getMinDummyValue()
    {
        int min = Integer.MAX_VALUE;

        for(int i=0; i<missing_runs.length; i++)
        {
            if(i != output_file_index && missing_runs[i] < min)
            {
                min = missing_runs[i];
            }
        }

        return min;
    }

    /**
    * Returns index of a file which according to distribution_array contains the minimum amount of runs.
    *
    * @return index of a file with minimum amount of runs.
    */
    private static int getMinFileIndex()
    {
        int min_file_index = -1;
        int min = Integer.MAX_VALUE;

        for(int i=0; i<distribution_array.length; i++)
        {
            if(distribution_array[i] != 0 && distribution_array[i] < min)
            {
                min_file_index = i;
            }
        }

        return min_file_index;
    }

    /**
    * Writes next string run to output file pointed by @param run_file_writer.
    * 
    * @param main_file_length length of the main input file.
    * @param main_file_reader reader used to read main input file.
    * @param run_file_writer  writer used to write to a specific output file
    * @param file_index       used to update missing_runs and run_last_elements arrays.
    *                         In case when main input file is read to the end amount of
    *                         dummy runs on this index in missing_runs array needs to be
    *                         decreased. When run is ended run_last_elements array on
    *                         this index is populated with the last element of the run.
    *                         
    */
    private static void writeNextStringRun(long main_file_length, BufferedReader main_file_reader, BufferedWriter run_file_writer, int file_index)
    {
        if(data_read >= main_file_length)
        {
            missing_runs[file_index]--;
            return;
        }

        try
        {
            if(next_run_element != null)
            {
                run_file_writer.write(next_run_element + "\n");             
                data_read += next_run_element.length() + 1;
            }

            String min_value = "";
            String current_line = main_file_reader.readLine();          

            /* Case if run is a single element: acordingly update variables and return */
            if(next_run_element != null)
            {               
                if(next_run_element.compareTo(current_line) > 0)
                {
                    run_last_elements[file_index] = next_run_element;
                    next_run_element = current_line;

                    return;
                }
            }

            while(current_line !=  null)
            {               
                if(current_line.compareTo(min_value) >= 0)
                {
                    run_file_writer.write(current_line + "\n");                 
                    data_read += current_line.length() + 1;

                    min_value = current_line;
                    current_line = main_file_reader.readLine();                 
                }

                else
                {
                    next_run_element = current_line;
                    run_last_elements[file_index] = min_value;

                    return;
                }
            }
        }
        catch(Exception e){}
    }

    /**
    * Checks if two adjacent runs have merged into a single run. It does this by comparing the first element
    * of the second run with the last element of the first run. If this two elements are in sorted order, the runs
    * have merged.
    * 
    * @param main_file_length length of the main input file.
    * @param file_index       index in array from which last element of the first run is taken for comparison.
    * @param first_element    first element of the second run to be taken into comparison.
    * @return true if the runs have merged, false instead.
    */
    private static boolean runsMerged(long main_file_length, int file_index, String first_element)
    {
        if(data_read < main_file_length && run_last_elements[file_index] != null && first_element != null)
        {           
            return run_last_elements[file_index].compareTo(first_element) <= 0 ? true:false;
        }
        return false;
    }

    /**
    * Calculates next run distribution level. The new level is calculated following
    * Finonacchi sequence rule.
    */
    private static void setNextDistributionLevel()
    {
        runs_per_level = 0;
        int current_distribution_array[] = distribution_array.clone();

        for(int i=0; i<current_distribution_array.length - 1; i++)
        {
            distribution_array[i] = current_distribution_array[0] + current_distribution_array[i+1];
            runs_per_level +=  distribution_array[i];
        }
    }

    /**
    * Calculates previous run distribution level. The new level is calculated following.
    * Finonacchi sequence rule.
    */
    private static void setPreviousRunDistributionLevel()
    {
        int diff;
        int current_distribution_array[] = distribution_array.clone();
        int last = current_distribution_array[current_distribution_array.length - 2];

        old_output_file_index = output_file_index;

        runs_per_level = 0;
        runs_per_level += last;
        distribution_array[0] = last;

        for(int i=current_distribution_array.length - 3; i>=0; i--)
        {
            diff = current_distribution_array[i] - last;
            distribution_array[i+1] = diff;
            runs_per_level += diff;
        }
    }

    /**
    * Calculates the amount of dummy runs for every input file after distribute phase of the algorithm.
    */
    private static void setMissingRunsArray()
    {   
        for(int i=0; i<distribution_array.length - 1; i++)
        {
            missing_runs[i] = (distribution_array[i] - missing_runs[i]);
        }
    }

    /**
    * Closes all file readers used to read from run files in distribute phase of the algorithm.
    * 
    * @param run_file_readers array of readers to read from run files.
    */
    private static void closeReaders(BufferedReader run_file_readers[])
    {
        try
        {
            for(int i=0; i<run_file_readers.length; i++)
            {
                run_file_readers[i].close();
            }
        }

        catch(Exception e){}
    }

    /**
    * Closes all file writers used to write to run files in distribute phase of the algorithm.
    * 
    * @param run_file_writers array of writers to write to run files.
    */
    private static void closeWriters(BufferedWriter run_file_writers[])
    {
        try
        {
            for(int i=0; i<run_file_writers.length; i++)
            {
                run_file_writers[i].close();
            }
        }

        catch(Exception e){}
    }

    /**
    * Clears all unnecessary temporary files and renames the sorted one to its final name.
    * 
    * @param working_dir path to working directory where entire sorting process is taking place.
    * @param main_file main input file.
    * @param temp_files number of temporary files to work with.
    */
    private static void clearTempFiles(String working_dir, File main_file, File temp_files[])
    {
        File sorted_file = new File(working_dir+"sorted.txt");

        for(int i=0; i<temp_files.length; i++)
        {
            if(temp_files[i].length() == main_file.length())
            {
                temp_files[i].renameTo(sorted_file);
                temp_files[i].delete();
            }

            temp_files[i].delete();
        }
    }   
}
\$\endgroup\$
  • 1
    \$\begingroup\$ (Welcome to CodeReview!) That is a lot of code: does it contain everything to reproduce the timing issues? Can you give an overview of the strategy used? (Beyond algorithm: are the files in tmp files on disks, SSD, cloud? Synchronous IO or not? (you import io, not nio?!) …) What are your findings about where wall clock time goes: key comparison? Waiting for file input? Output? Copying records from buffer to buffer? (For laughs: PQ operations?) How did you establish temporal performance? What can you say about the input: number of records and distribution of key length & record size? \$\endgroup\$ – greybeard Mar 13 at 6:00
  • 1
    \$\begingroup\$ (Can't remember seeing source on CR before that made me think running javadoc is bound to provide me with food for thought if not insight: well done!) \$\endgroup\$ – greybeard Mar 13 at 6:10
  • \$\begingroup\$ @greybeard this is all the code I have. What do you mean by "strategy used"? All the temporary files that algorithm works with are stored on a local WD Blue 1 TB HDD with 16 MB of cache. The main input file for the algorithm is .txt file with strings of a random lengths (1-15) separated by a new line character. All the files that algorithm works with (temp files, main input file, final sorted file) are stored in the same directory defined by working_dir variable. There is no special order defined for the main file - it is randomly distributed. \$\endgroup\$ – henrich Mar 13 at 7:57
  • \$\begingroup\$ I don't have useful idea why it works so slow. Key (string) comparison is by default slow since comparing strings right? One idea is that writing is somehow slow (despite I am using BufferedWritter and BufferedReader). There is no special wait for input/output file(s), it is just the sort phase that needs to finish. Just an example of timing: sorting txt file with 134217728 lines (786 MB) takes about 260 second. If running the algorithm in loop for about 10 times, this time stabilises at around 230 seconds. I can link the file if needed? \$\endgroup\$ – henrich Mar 13 at 8:20
  • \$\begingroup\$ main input […] is .txt file with strings of a random lengths (1-15) … This looks generated file: rather than linking to such a file, include the generator source. Strategy: I gave two examples of what hoping for whys, more: how many files to use (symmetric merge can be expected to use less passes above 8), "character set" or unicode I/O. How did you establish distribution phase works just fine without any performance issues and merge phase […] major issue […] still present? \$\endgroup\$ – greybeard Mar 14 at 6:53
1
\$\begingroup\$

The algorithm works as expected …

How do you know? Sketch what tests you did how.

…but it is very slow.

My current take: due to Exception handling, due in turn to not working as specified.
(Test input: download of norvig.com/big.txt - loads of NullPointerException trying to dereference next_run_first_elements[i].)


For every class where instances can be expected to turn up in arrays, collections and such, override toString():

@Override
public String toString() {
    return new StringBuilder().append(value)
        .append('#').append(file_index).toString();
}

I failed to come up with a good summary of what setNextDistributionLevel() and setPreviousRunDistributionLevel() do, which is why I present the 1st without doc comment. (The naming is inconsistent.)

private static void setNextDistributionLevel()
{
    final int
        ways_1 = distribution_array.length - 2,
        diff = distribution_array[0];
    for (int i = 0, next ; i <= ways_1 ; i = next)
        distribution_array[i] = distribution_array[next = i+1] + diff;
    runs_per_level += diff * ways_1;
    // System.out.println("next " + runs_per_level + ": " + Arrays.toString(distribution_array));
}

/**
* Calculates previous run distribution level:
* every number of runs is smaller than in the previous level
*  by the smallest number therein */// ToDo: describe commendably
private static void setPreviousRunDistributionLevel()
{
    final int 
        ways_1 = distribution_array.length - 2,
        diff = distribution_array[ways_1];

    for (int i = ways_1, next ; 0 < i ; i = next)
        distribution_array[i] = distribution_array[next = i-1] - diff;
    runs_per_level -= diff * ways_1;
    distribution_array[0] = diff;
    // System.out.println("prev " + runs_per_level + ": " + Arrays.toString(distribution_array));
}

closeReaders() & closeWriters() contain repeated code and don't live up to their documentation in case of an exception - suggestion:

/** Closes all Writers in <code>run_file_writers</code>. */
private static void closeWriters(BufferedWriter run_file_writers[]) {
    closeAll(run_file_writers);
}

/** Closes all <code>candidates</code>. */
private static void closeAll(Closeable candidates[]) {
    for (Closeable candidate: candidates)
        try {
            candidate.close();
        } catch (Exception e) {
        }
}

Use the runtime environmnt's support in favour of open coding, e.g. Arrays.fill() instead of iterating over array indices to assign to elements.

\$\endgroup\$
  • \$\begingroup\$ (Musing doing a full code review once the question supports reproduction of timing issues.) \$\endgroup\$ – greybeard Mar 13 at 7:26
  • \$\begingroup\$ Guesses about causes for unsatisfactory speed: 1) Not creating initial runs of max. achievable size (1st sentence of en.wikipedia's article…) 2) Choice of algorithm. Polyphase merge looked a Good Idea when when your computing centre had nine tape drives (four fast, two of the sluggish not able to read backwards, two of the fast ones able to write backwards (and two dead ones for spares) - and at any given time, seven could be expected in working condition, but at most five available for data tapes of any single job of a mere mortal). \$\endgroup\$ – greybeard Mar 14 at 7:25
  • \$\begingroup\$ Regarding 1): I am not sure if I understand what seems to be a problem with initial runs and their max. achievable size? I just distribute the runs following distribution array. Regarding 2): since I am comparing this algorithm with other external sorting algorithms, the choice is not really a question. I have applied your suggestion with closeables, will also change IO for NIO. Have you noticed any other issues in the code? Thanks. \$\endgroup\$ – henrich Mar 14 at 8:06
  • \$\begingroup\$ 3) using too few files 4) using buffers no larger than the smallish default size. (More) Things that justifying experimentation: a) using unicode in temp files instead of en-/decoding time&again b) asynchronous I/O \$\endgroup\$ – greybeard Mar 14 at 8:43
  • \$\begingroup\$ I just distribute the runs detected in the input - which would be the thing to do in the internal sort algorithm natural merge. For an external merge, use the biggest PQ you can justify to create initial runs with an expected length about twice the capacity of that PQ, and proportionally fewer of those. (Say 1GB for a PQ of 9 char Strings - I'd expect runs of about 50E6 records, as opposed to 1.5 for "natural" - a factor of about 30E6. With an approximate reduction factor of 4.3 for a 20 file polyphase merge, that's almost 12 passes saved.) \$\endgroup\$ – greybeard Mar 14 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.