Search code examples
algorithmsortingmergesort

Merge sort comparisons


How do we merge 4 sorted files containing 50, 10, 25 and 15 records ? Because selecting the order of merging will reduce/increase the number of comparisons made.


Solution

  • For a single merge, the number of comparisons depends on the record values, anywhere from 1 to the sum of the lengths of both files.

    I would advise to merge the 10 and 15 record files first, then merge the resulting file with the 25 record file and finally merge the resulting 50 record file with the first 50 record file.

    You could also implement a 4 way merge and merge all 4 files in parallel.

    Keep in mind that the file lengths are very small, so the number of comparisons is not going to matter much for the final performance.