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?