An Efficient External Sort Algorithm with no Additional Space
W. R. Dufrene, F. C. Lin · The Computer Journal · 1992
In analogy to the Internal Bubble Sort we have developed an external sort paradigm which when implemented proves to be significantly faster than the Friedman/Lin external sort and faster than the Merge-Sort under certain conditions. Its time complexity is estimated to be (N^2 Log N) or better. Possible refinements are also mentioned.