3 ms·
sort(1) is a merge sort (specifically, an "external R-way merge")—and, as a merge sort, it actually isn't constrained by memory. It spills its sorted intermedia
by derefr 8y ago
sort(1) is a merge sort (specifically, an "external R-way merge")—and, as a merge sort, it actually isn't constrained by memory. It spills its sorted intermediates to disk as temp files! (And, in fact, it even compresses each intermediate, for the same reason a column store like Cassandra does.) It's pretty optimal!
If you're wondering how this is at-all fast (and it is), in Linux at least /tmp is a tmpfs, meaning that these tempfiles are actually ending up as memory after all. They get "spilled to disk" in the sense that the memory associated with the files spills to swap; but, importantly, tmpfs pages know that they're from files, so they have much better swapping semantics than regular memory for the case where you're writing the file as a stream, and then reading it as a stream. (Basically, juggling streams under a tmpfs is equivalent in overhead to managing memory when you've got it, and managing files when you don't, but without any of the dev-time overhead of having to write code for both cases.)