I am aware of some sorting algorithms and there pros and cons but my question is specifically: What is a good sorting algorithm for a list that is generally but not strictly increasing, i.e. 1 5 4 8 5 8 9 9 9 12 12 16 18 17 20 15 19 18 20 21 23 21 27 25 26 30 31 33 29 34 35 31 35 38 37 37 37 37 40 41 41 45 47 43 50 48 52 49 50
I'm not sure about the properties of the actual data I will be using, there may be much less deviation from a strictly increasing list, i.e. only a few percent of elements out of order.
An obvious strategy of reasonable practical efficiency (he claims, hand-wavingly) would be to filter out the decreasing elements as they're encountered leaving a non-decreasing list $N$. Sort the filtered elements (using the same method since they're still roughly ascending) and merge back into $N$. In your example you'd filter out the parenthesised elements:
1 5 (4) 8 (5) 8 9 9 9 12 12 16 18 17 20 (15) (19) (18) 20 21 23 (21) 27 (25) 26 30 31 33 (29) 34 35 (31) 35 38 37 37 37 37 40 41 41 45 47 (43) 50 (48) 52 (49) (50)
leaving
1 5 8 8 9 9 9 12 12 16 18 17 20 20 21 23 27 26 30 31 33 34 35 35 38 37 37 37 37 40 41 41 45 47 50 52
and the filtered elements in the order:
4 5 15 [19] 18 21 25 29 31 43 48 49 50
with only one element out of order in the filtered elements.
The filtering and merging operations are $O(n)$. If a constant fraction $r$ of elements were filtered at each level, the complexity is roughly $n(1 + r + r^2 + \cdots)$ which is $O(n)$-ish (he said, hedging his bets because of the rustiness of his complexity theory).