How does sorting a smaller (auxiliary) array do quicksort faster?

Question

I heard that in quicksort it is better to call recursion on a smaller subarray first. For example, if 5 was a pivot point, and the data is sorted to 4,1,3,5,7,6 , then it is better to sort the subarray 7,6 , because it contains two elements, where as 4,1,3 contains three .

The source of all knowledge provides pseudo code for quick sorting.

 quicksort(A, i, k): if i < k: p := partition(A, i, k) quicksort(A, i, p - 1) quicksort(A, p + 1, k) 

Thus, an algorithm that will implement off for recursion on a smaller array will look something like this:

 quicksort(A, i, k): if i < k: p := partition(A, i, k) if(pi > kp) /*difference from start point to pivot is greater than difference from pivot to end point*/ quicksort(A, p + 1, k) quicksort(A, i, p - 1) else quicksort(A, i, p - 1) quicksort(A, p + 1, k) 

I wrote code like this written in Java and it seems to be faster, but why? At first I thought it was due to tail recursion optimization, but then I realized that it was wrong, because Java does not support it.

Why sort code in a smaller subarray first? This article claims that it should be

Answer 1

Maybe something is missing for me here, but if you recurs on your two affairs in a different order, you simply cross the depth of the recursion tree - first after the potential execution of some swaps of the child subtrees on each node, but it is still isomorphic to the original recursion tree, and the set of all recursion depths for the base cases will still be the same. The only way I can see an obvious decrease in recursion depth or other acceleration associated with recursion is something like you recurs on a smaller subarray and then select the axis for the larger subarray (without recursion) and then recurs into two basements for a larger subarray. This will turn your recursion tree into a triple recursion tree instead of binary, which usually should have a smaller maximum depth.

Answer 2

The Java JIT compiler can eliminate tail recursion, which reduces stack memory usage. Reduced stack memory can reduce cache pressure, which allows you to increase the partition size to a higher cache level.

Another minor improvement is the reduction in the number of function calls. This is a slight reduction in the number of commands executed. But reducing the number of instructions usually has a very low correlation with performance when working with data that is not suitable for caching.

Answer 3

I recently watched a conversation by Leslie Lamport in which he pointed out that Quicksort, as originally presented, is not necessarily a recursive algorithm, although many programmers prefer to implement it recursively.

Instead of recursing into sections, you can simply add them to the range queue, which still needs to be sorted. The algorithm iterates until the queue is empty. Whether you will push and drag a range from the head or tail determines whether you will advance depth - first or width - first.

 quicksort(a, begin, end) { queue<range> q; push q(range(begin, end)); while (!q.empty()) { range = q.pop_front(); pivot = partition(a, range.begin, range.end); if (pivot > range.begin) q.push_back(range(range.begin, mid)); if (pivot + 1 < range.end) q.push_back(range(mid + 1, range.end)); } } 

A recursive implementation simply uses the stack as a LIFO queue, and therefore naturally occurs with depth in the first order, and I really don't think it matters which side you process next. Queue length is still limited by recursive depth.

But if you work in the first order using the FIFO queue, as shown in the pseudo code, then the order may matter. A larger section will add more subbands to the queue, so you would prefer to do this side as soon as the queue is as small as possible. To make the queue smaller, you want to handle the smaller sub-range first.