Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In divide and conquer algorithms such as quicksort and mergesort, the input is usually (at least in introductory texts) split in two, and the two smaller data sets are then dealt with recursively. It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set. But why not split the data set in three parts? Four? n?

I guess the work of splitting the data in many, many sub sets makes it not worth it, but I am lacking the intuition to see that one should stop at two sub sets.

I have also seen many references to 3-way quicksort. When is this faster? What is used in practice?

share|improve this question

3 Answers 3

up vote 34 down vote accepted

It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set.

That is not the essence of divide-and-conquer algorithms. Usually the point is that the algorithms cannot "deal with the whole data set" at all. Instead, it is divided into pieces that are trivial to solve (like sorting two numbers), then those are solved trivially and the results recombined in a way that yields a solution for the full data set.

But why not split the data set in three parts? Four? n?

Mainly because splitting it into more than two parts and recombining more than two results results in a more complex implementation but doesn't change the fundamental (Big O) characteristic of the algorithm - the difference is a constant factor, and may result in a slowdown if the division and recombination of more than 2 subsets creates additional overhead.

For example, if you do a 3-way merge sort, then in the recombination phase you now have to find the biggest of 3 elements for every element, which requires 2 comparisons instead of 1, so you'll do twice as many comparisons overall. In exchange, you reduce the recursion depth by a factor of ln(2)/ln(3) == 0.63, so you have 37% fewer swaps, but 2*0.69 == 26% more comparisons (and memory accesses). Whether that is good or bad depends on which is more expensive in your hardware.

I have also seen many references to 3-way quicksort. When is this faster?

Apparently a dual pivot variant of quicksort can be proven to require the same number of comparisons but on average 20% fewer swaps, so it's a net gain.

What is used in practice?

These days hardly anyone programs their own sorting algorithms anymore; they use one provided by a library. For example, the Java 7 API actually uses the dual-pivot quicksort.

People who actually do program their own sorting algorithm for some reason will tend to stick to the simple 2-way variant because less potential for errors beats 20% better performance most of the time. Remember: by far the most important performance improvement is when the code goes from "not working" to "working".

share|improve this answer
1  
Small note: Java 7 uses Dual-Pivot quicksort only when sorting primitives. To sort objects it uses Timsort. –  Bakuriu May 5 '13 at 22:17
    
+1 for "These days hardly anyone programs their own sorting algorithms anymore" and (more importantly) "Remember: by far the most important performance improvement is when the code goes from "not working" to "working"." However, I would like to know if that overhead is still trivial if, for example, one splits the data set into many, many parts. As it so happens, so have other people: bealto.com/gpu-sorting_intro.html stackoverflow.com/questions/1415679/… devgurus.amd.com/thread/157159 –  AndrewJacksonZA May 8 '13 at 8:37

Asymptotically speaking, it doesn't matter. For example, binary search makes approximately log_2 n comparisons, and ternary search makes approximately log_3 n comparisons. If you know your logarithms, you know that log_a x = log_b x / log_b a, so binary search only makes about 1 / log_3 2 ~= 1.5 times as many comparisons as ternary search. This is also the reason nobody ever specifies the base of the logarithm in big Oh notation: It's always a constant factor away from the logarithm in a given base, no matter what the base actual is. So splitting the problem into more subsets doesn't improve time complexity and practically isn't enough to outweigh the more complex logic. In fact, that complexity may affect practical performance negatively, increasing cache pressure or making micro-optimizations less infeasible.

On the other hand, some tree-ish data structure do use a high branching factor (much bigger than 3, often 32 or more), though usually for other reasons. It improves utilization of the memory hierarchy: data structures stored in RAM make better use of the cache, data structures stored on disk require fewer reads HDD->RAM.

share|improve this answer

There are search/sort algorithms that subdivide not by two, but by N.

A simple example is search by hash coding, which takes O(1) time.

If the hash function is order-preserving, it can be used to make an O(N) sort algorithm. (You can think of any sort algorithm as just doing N searches for where a number should go in the result.)

The fundamental issue is, when a program examines some data and then enters some following states, how many following states are there, and how close to equal are their probabilities?

When a computer does a comparison of two numbers, say, and then either jumps or not, if both paths are equally likely, the program counter "knows" one more bit of information on each path, so on average it has "learned" one bit. If a problem requires that M bits be learned, then using binary decisions it can't get the answer in fewer than M decisions. So, for example, looking up a number in a sorted table of size 1024 can't be done in fewer that 10 binary decisions, if only because any fewer would not have enough outcomes, but it can certainly be done in more than that.

When a computer takes one number and transforms it into an index into an array, it "learns" up to log base 2 of the number of elements in the array, and it does it in constant time. For example, if there is a jump table of 1024 entries, all more or less equally likely, then jumping through that table "learns" 10 bits. That's the fundamental trick behind hash coding. A sorting example of this is how you can sort a deck of cards. Have 52 bins, one for each card. Fling each card into its bin, and then scoop them all up. No subdividing required.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.