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.

Interview Answer

6 Answers


Vector sort.

Interview Candidate on Mar 19, 2009

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

A Balanced Tree sort on May 5, 2009

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

Eric Goff on May 5, 2009

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

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

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.