3 ms·

They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.

• 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 ago
    Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
    • touisteur 5y ago
      Which is where you get problematic tail latencies. Or your data fits on the stack.
  • phkahler 5y ago
    Heapsort 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.