Interview Question

Senior Software Engineer Interview

-Boulder, CO

Google

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

Answer

Interview Answers

6 Answers

5

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

3

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

Eric Goff on

0

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

0

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

Anonymous on

1

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

A Balanced Tree sort on

0

Vector sort.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.