Sorting a Random Access File in situ
H. W. Six · The Computer Journal · 1984
To sort an external file on a random access device, the merge sort is the generally accepted method. We present a new algorithm based on Quicksort which allows sorting of external files in situ. Analytical results and a comparison of test runs indicate that when the new algorithm is applied to a file with suitable key structure, it is competitive to the merge sort in terms of run-time behaviour.