Efficiency of Sort Algorithms

Question

I am studying up for a pretty important interview tomorrow and there is one thing that I have a great deal of trouble with: Sorting algorithms and BigO efficiencies.

What number is important to know? The best, worst, or average efficiency?

Answer 1

worst, followed by average. be aware of the real-world impact of the so-called "hidden constants" too - for instance, the classic quicksort algorithm is O(n^2) in the worst case, and O(n log n) on average, whereas mergesort is O(n log n) in the worst case, but quicksort will outperform mergesort in practice.

Answer 2

All of them are important to know, of course. You have to understand the benefits of one sort algorithm in the average case can become a terrible deficit in the worst case, or the worst case isn't that bad, but the best case isn't that good, and it only works well on unsorted data, etc.

Answer 3

In short.

Sorting algorithm efficiency will vary on input data and task.

• sorting max speed, that can be archived is n*log(n)
• if data contains sorted sub data, max speed can be better then n*log(n)
• if data consists of duplicates, sorting can be done in near linear time
• most of sorting algorithms have their uses

Most of quick sort variants have its average case also n*log(n), but thy are usually faster then other not heavily optimized algorithms. It is faster when it is not stable, but stable variants are only a fraction slower. Main problem is worst case. Best casual fix is Introsort.

Most of merge sort variants have its best, average and worst case fixed to n*log(n). It is stable and relatively easy to scale up. BUT it needs a binary tree (or its emulation) with relative to the size of total items. Main problem is memory. Best casual fix is timsort.

Sorting algorithms vary also by size of input. I can make a newbie claim, that over 10T size data input, there is no match for merge sort variants.

Answer 4

I recommend that you don't merely memorize these factoids. Learn why they are what they are. If I was interviewing you, I would make sure to ask questions that show my you understand how to analyze an algorithm, not just can spit back out something you saw on a webpage or in a book. Additionally, the day before an interview is not the time to be doing this studying.

I wish you the best of luck!! Please report back in a comment how it went!

Answer 5

I am over with one set of interviews at my college just now...

Every algorithm has its benefits, otherwise it wont exist. So, its better to understand what is so good with the algorithm that you are studying. Where does it do well? How can it be improved?

I guess you'll automatically need to read various efficiency notations when you do this. Mind the worst case, and pay attention to the average case, best cases are rare.

All the best for your interview.

Answer 6

You may also want to look into other types of sorting that can be used when certain conditions exist. For example, consider Radix sort. http://en.wikipedia.org/wiki/Radix_sort