Google Interview Question: What sort would you use if yo... | Glassdoor

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.
Answer

Interview Answer

6 Answers

0

Vector sort.

Interview Candidate on Mar 19, 2009
1

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

A Balanced Tree sort on May 5, 2009
1

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

Eric Goff on May 5, 2009
4

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 Apr 11, 2011
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 Sep 28, 2014
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 Jul 3, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.