A SIGMOD 2014 paper from Microsoft Research states that the "importance of sorting almost sorted data quickly has just emerged over the last decade", and goes on to propose variants of Patience sort and Linear Merge, and measure their performance on synthetic "close to sorted" data.

It seems to me that this description matches the theme of "Adaptive Sorting", covering algorithms taking advantage of existing preorder in sequences to be sorted, which has been the topic of various publications (albeit in the community of theoretical computer science rather than databases) from as early as 1979:

 - 1979-CTCS Sorting Presorted Files - Mehlhorn
 - 1980-CACM Best Sorting Algorithm For Nearly Sorted Lists - Cook, Kim
 - 1985-TCom Measures Of Presortedness And Optimal Sorting Algorithms - Mannila
 - 1992-ACMCS ASurvey Of Adaptive Sorting Algorithms - Estivill-Castro, Wood
 - 1994-IC Sorting Shuffled Monotone Sequences- Levcopoulos, Petersson
 - 1995-DAM A Framework For Adaptive Sorting - Petersson, Moffat

Am I missing a key difference between those approaches or is it a mere occurrence of weak communication between the database and TCS communities?

  • $\begingroup$ I would guess the difference is if we are allowed to assume a priori that the input has some structure, i.e. can I assume that the input is almost sorted or do I need to discover it is almost sorted? $\endgroup$
    – Kaveh
    Jun 27, 2014 at 23:57

1 Answer 1


I think the importance of "sorting almost sorted data quickly" in the database community is because of good streaming and/or parallel algorithms for k-sorting and for k-sorted id generation. (e.g. http://link.springer.com/chapter/10.1007%2F978-3-540-77050-3_2#page-1) Adaptive sorting is a more general topic: for instance, reverse order would not be what the database community cares about, but would be perfectly reasonable to exploit more generally.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.