3 ms·
Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard'
by touisteur 5y ago
Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.
- karpierz 5y agoMergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
- touisteur 5y agoWhich is where you get problematic tail latencies. Or your data fits on the stack.
- phkahler 5y agoHeapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again). Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.