For disk files, an external sort based on partitioning similar to quicksort is possible. It is slower than external merge sort, but doesn't require extra disk space. 4 buffers are used, 2 for input, 2 for output. Let N<math> N= </math> number of records in the file, <math> B = </math> the number of records per buffer, and <math> M = N/B = </math> the number of buffer segments in the file. Data is read (and written) from both ends of the file inwards. Let <math> X </math> represent the segments that start at the beginning of the file and <math> Y </math> represent segments that start at the end of the file. Data is read into the <math> X </math> and <math> Y </math> read buffers. A pivot record is chosen and the records in the <math> X </math> and <math> Y </math> buffers other than the pivot record are copied to the <math> X </math> write buffer in ascending order and <math> Y </math> write buffer in descending order based comparison with the pivot record. Once either <math> X </math> or <math> Y </math> buffer is filled, it is written to the file and the next <math> X </math> or <math> Y </math> buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an <math> X </math> write buffer, the pivot record is appended to it and the <math> X </math> buffer written. If that buffer is a <math> Y </math> write buffer, the pivot record is prepended to the <math> Y </math> buffer and the <math> Y </math> buffer written. This constitutes one partition step of the file, and the file is now composed of two subfiles. The start and end positions of each subfile are pushed/popped to a stand-alone stack or the main stack via recursion. To limit stack space to <math> O(log2\log_2(n)) </math>, the smaller subfile is processed first. For a stand-alone stack, push the larger subfile parameters onto the stack, iterate on the smaller subfile. For recursion, recurse on the smaller subfile first, then iterate to handle the larger subfile. Once a sub-file is less than or equal to 4 B records, the subfile is sorted in-place via quicksort and written. That subfile is now sorted and in place in the file. The process is continued until all sub-files are sorted and in place. The average number of passes on the file is approximately <math> \frac{1 + \ln(N+1)/}{(4 B)} </math>, but worst case pattern is <math> N </math> passes (equivalent to <math> O(n^2) </math> for worst case internal sort).<ref>{{citation| title=An efficient external sorting with minimal space requirement| author1=Motzkin, D.| author2=Hansen, C.L.| journal=International Journal of Computer and Information Sciences| volume=11| pages=381–396| date=1982| issue=6| doi=10.1007/BF00996816| s2cid=6829805}}</ref>
