KEY NOT FOUND: coverImgAlt
Best Places to Work 2022


Engaged Employer


Add an Interview

Interview Question

Senior Software Engineer Interview

-Boulder, CO


What sort would you use if you required tight max time bounds and wanted highly regular performance.

AnswerAdd Tags

Interview Answers

6 Answers


Merge sort and heapsort are always guaranteed to be n*log(n). Quicksort is usually faster on the average but can be as bad as O(n^2), although with very low probability. Heapsort also does it sorting in-place, without needing an extra buffer, like mergesort. Lastly, heapsort is much easier to implement and understand than balancing trees mentioned by earlier posts.

O.A. on


That is so say, a "Balanced Tree Sort" is guaranteed to be O(n log n) always.

Eric Goff on


for something like this you generally want bubble sort or insertion sort. It's not about being fast it's about being consistent. Make it do exactly the same thing every time.

Anonymous on


Use a sorting network. There's some precomputation time, but runtime will be very consistent (the only variability is branch prediction performance)

Anonymous on


Guaranteed to be O(n log n) performance. No better, no worse.

A Balanced Tree sort on


Vector sort.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.