递归算法快速排序（归并与快速排序中的分治与递归算法思想）

递归算法快速排序（归并与快速排序中的分治与递归算法思想）1 归并排序快速排序：不断以基准值二分数组（大于基准值的放到一端，小于基准值的放到另一端），直到规模为1。归并和快速排序都充分体现了分治和双递归的算法思想，并且具有较高的时间效率。③ 以递归调用语句为基准，此语句前面的语句形成递归前进段，后面的语句形成递归回归段；如果函数参数有迭代关系，与简单的循环语句不同，递归函数的语句是分段执行的；④ 递归语句分单递归，双递归及多递归等；单递归是指递归函数自己调用自己一次，双递归是调用两次，多递归是调用多次；双递归的调用形成一种二叉树的调用关系；归并排序：不断二分数组规模，直至分解数组到规模为1，然后不断合并有序数组；

分治：分而治之，divide and conquer；将复杂的问题进行分解，分解到可以简而解之，需要时，再治（conquer)，将全部子问题的解合并为整个的解;

递归：一些复杂问题，分解后各子问题的解法与整体问题的解法具有相同结构（相同解法），同样的代码可以重复调用（自己调用自己）。函数递归调用时，通常有4个特点：

① 有一个递归终止条件，通常此条件的问题的解的规模为1时，可直观求解；

② 递归函数的参数可以形成迭代关系，向递归递归终止条件收敛；

③ 以递归调用语句为基准，此语句前面的语句形成递归前进段，后面的语句形成递归回归段；如果函数参数有迭代关系，与简单的循环语句不同，递归函数的语句是分段执行的；

④ 递归语句分单递归，双递归及多递归等；单递归是指递归函数自己调用自己一次，双递归是调用两次，多递归是调用多次；双递归的调用形成一种二叉树的调用关系；

归并排序：不断二分数组规模，直至分解数组到规模为1，然后不断合并有序数组；

快速排序：不断以基准值二分数组（大于基准值的放到一端，小于基准值的放到另一端），直到规模为1。归并和快速排序都充分体现了分治和双递归的算法思想，并且具有较高的时间效率。

1 归并排序

Consider again the problem of sorting a list of n items in ascending order. We will illustrate our ideas with a list of integers. We now show how to use recursion and merging to sort a list. Consider this:

sort a list sort first half of list sort second half of list merge sorted halves into one sorted list end sort

Clearly if we can sort the two halves and then merge them we will have a sorted list. But how do we sort the halves? We use the same method! Here’s an example:

sort first half of list sort first half of first half of list (one quarter of the original list) sort second half of first half of list (one quarter of the original list) merge sorted halves into one sorted list end sort

For each piece we have to sort we break it into halves sort the halves and merge them. When do we stop using this process on a piece? When the piece consists of one element only there is nothing to do to sort one element.

We can modify our algorithm as follows:

sort a list if the list contains more than one element then sort first half of list sort second half of list merge sorted halves into one sorted list end if end sort

We assume the list is stored in an array A from A[lo] to A[hi]. We can code the algorithm as a C function as follows:

void mergeSort(int A[] int lo int hi) { void merge(int[] int int int); if (lo < hi) { //list contains at least 2 elements int mid = (lo hi) / 2; //get the mid-point subscript mergeSort(A lo mid); //sort first half mergeSort(A mid 1 hi); //sort second half merge(A lo mid hi); //merge sorted halves } }// 前分后并

This assumes that merge is available and the following statement will merge the sorted pieces in A[lo..mid] and A[mid 1..hi] so that A[lo..hi] is sorted:

merge(A lo mid hi);

We will show how to write merge shortly.

But first we show how this function sorts the following list stored in an array num:

The function will be called with:

mergeSort(num 0 6);

In the function num will be known as A lo will be 0 and hi will be 6. From these mid will be calculated as 3 giving rise to two calls.

mergeSort(A 0 3); mergeSort(A 4 6);

Assuming that the first will sort A[0..3] and the second will sort A[4..6] we will have the following result:

merge will merge the pieces to produce:

Each of these calls will give rise to two further calls. The first will produce:

mergeSort(A 0 1); mergeSort(A 2 3);

The second will produce:

mergeSort(A 4 5); mergeSort(A 6 6);

As long as lo is less than hi two further calls will be produced. If lo is equal to hi the list consists of one element only and the function simply returns. The following shows all the calls generated by the initial call to mergeSort in the order in which they are generated:

mergeSort(A 0 6) mergeSort(A 0 3) mergeSort(A 0 1); mergeSort(A 0 0); mergeSort(A 1 1); mergeSort(A 2 3); mergeSort(A 2 2); mergeSort(A 3 3); mergeSort(A 4 6); mergeSort(A 4 5); mergeSort(A 4 4); mergeSort(A 5 5); mergeSort(A 6 6);

To complete the job we need to write merge. We can describe merge as follows:

void merge(int A[] int lo int mid int hi) { //A[lo..mid] and A[mid 1..hi] are sorted; //merge the pieces so that A[lo..hi] are sorted

Note what must be done: we must merge two adjacent portions of A back into the same locations. The problem with this is that we cannot merge into the same locations while the merge is being performed since we may overwrite numbers before they are used. We will have to merge into another (temporary) array and then copy the merged elements back into the original locations in A.

We will use a temporary array called T; we just need to make sure it is big enough to hold the merged elements.

This implies it must be at least as big as the array to be sorted. In merge we will denote its size by the symbolic constant MaxSize. Here is merge:

void merge(int A[] int lo int mid int hi) { //A[lo……mid] and A[mid 1……hi] are sorted ascending; //merge the pieces so that A[lo……hi] are sorted ascending int T[MaxSize]; int i = lo; // to subscript the first part of A : A[lo……mid] int j = mid 1; // to subscript the second part of A : A[mid 1……hi] int k = lo; // and k to subscript T while (i <= mid || j <= hi) { if (i > mid) // A[lo……mid] part is already processed T[k ] = A[j ];// then process the surplus of A[mid 1……hi] else if (j > hi) // A[mid 1……hi] part is already processed T[k ] = A[i ];// then process the surplus of A[lo……mid] else if (A[i] < A[j]) // sorted ascending the smaller is process preferentially T[k ] = A[i ]; else T[k ] = A[j ]; } for (j = lo; j <= hi; j ) A[j] = T[j]; mergeFuncCalledSize ; // 调试用 printArr(A n); // 调试用 }

We use i to subscript the first part of A j to subscript the second part and k to subscript T. The function merges A[lo..mid] and A[mid 1..hi] into T[lo..hi].

The while loop expresses the following logic: as long as we haven’t processed all the elements in both parts we enter the loop.

If we are finished with the first part (i > mid) copy an element from the second part to T. (Since (i > mid) would continue to remain true each time through the loop we will end up copying the remaining elements from the second part to T.)

If we are finished with the second part (j > hi) copy an element from the first part to T. (Since (j > hi) would continue to remain true each time through the loop we will end up copying the remaining elements from the first part to T.)

Otherwise we copy the smaller of A[i] and A[j] to T.

At the end we copy the elements from T to the corresponding locations in A.

The complete code:

#include <stdio.h> #define MaxSize 20 int num[] = {4 8 6 16 1 9 14 2 3 5 18 13 17 7 12 11 15 10}; int n = sizeof num / sizeof *num; void mergeSort(int[] int int); void printArr(int num[] int n); int static mergeFuncCalledSize = 0; // 调试用 void merge(int A[] int lo int mid int hi) { //A[lo……mid] and A[mid 1……hi] are sorted ascending; //merge the pieces so that A[lo……hi] are sorted ascending int T[MaxSize]; int i = lo; // to subscript the first part of A : A[lo……mid] int j = mid 1; // to subscript the second part of A : A[mid 1……hi] int k = lo; // and k to subscript T while (i <= mid || j <= hi) { if (i > mid) // A[lo……mid] part is already processed T[k ] = A[j ];// then process the surplus of A[mid 1……hi] else if (j > hi) // A[mid 1……hi] part is already processed T[k ] = A[i ];// then process the surplus of A[lo……mid] else if (A[i] < A[j]) // sorted ascending the smaller is process preferentially T[k ] = A[i ]; else T[k ] = A[j ]; } for (j = lo; j <= hi; j ) A[j] = T[j]; mergeFuncCalledSize ; // 调试用 printArr(A n); // 调试用 } int main() { printArr(num n); mergeSort(num 0 n-1); printArr(num n); printf("临时数组T在栈区被开辟了%d次！\n" mergeFuncCalledSize); printf("排序的数组元素的个数：%d\n" n); printf("要避免临时数组T在栈区重复分配内存空间，可以声明为局部static\n"); getchar(); return 0; } void mergeSort(int A[] int lo int hi) { void merge(int[] int int int); if (lo < hi) { //list contains at least 2 elements int mid = (lo hi) / 2; //get the mid-point subscript mergeSort(A lo mid); //sort first half mergeSort(A mid 1 hi); //sort second half merge(A lo mid hi); //merge sorted halves } } void printArr(int num[] int n) { for (int h = 0; h < n; h ) printf("%d " num[h]); printf("\n\n"); } /*output: 4 8 6 16 1 9 14 2 3 5 18 13 17 7 12 11 15 10 4 8 6 16 1 9 14 2 3 5 18 13 17 7 12 11 15 10 4 6 8 16 1 9 14 2 3 5 18 13 17 7 12 11 15 10 4 6 8 1 16 9 14 2 3 5 18 13 17 7 12 11 15 10 1 4 6 8 16 9 14 2 3 5 18 13 17 7 12 11 15 10 1 4 6 8 16 9 14 2 3 5 18 13 17 7 12 11 15 10 1 4 6 8 16 9 14 2 3 5 18 13 17 7 12 11 15 10 1 4 6 8 16 2 3 9 14 5 18 13 17 7 12 11 15 10 1 2 3 4 6 8 9 14 16 5 18 13 17 7 12 11 15 10 1 2 3 4 6 8 9 14 16 5 18 13 17 7 12 11 15 10 1 2 3 4 6 8 9 14 16 5 13 18 17 7 12 11 15 10 1 2 3 4 6 8 9 14 16 5 13 18 7 17 12 11 15 10 1 2 3 4 6 8 9 14 16 5 7 13 17 18 12 11 15 10 1 2 3 4 6 8 9 14 16 5 7 13 17 18 11 12 15 10 1 2 3 4 6 8 9 14 16 5 7 13 17 18 11 12 10 15 1 2 3 4 6 8 9 14 16 5 7 13 17 18 10 11 12 15 1 2 3 4 6 8 9 14 16 5 7 10 11 12 13 15 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 临时数组T在栈区被开辟了17次！ 排序的数组元素的个数：18 要避免临时数组T在栈区重复分配内存空间，可以声明为局部static */

2 quick sort

At the heart of quicksort is the notion of partitioning the list with respect to one of the values called a pivot. For example given the following list to be sorted:

we can partition it with respect to the first value 53. This means placing 53 in such a position that all values to the left of it are smaller and all values to the right are greater than or equal to it. Shortly we will describe an algorithm that will partition the above array as follows:

The value 53 is used as the pivot. It is placed in position 6. All values to the left of 53 are smaller than 53 and all values to the right are greater. The location in which the pivot is placed is called the division point (dp say). By definition 53 is in its final sorted position.

If we can sort num[1..dp-1] and num[dp 1..n] we would have sorted the entire list. But we can use the same process to sort these pieces indicating that a recursive procedure is appropriate.

Assuming a function partition is available that partitions a given section of an array and returns the division point we can write quicksort as follows:

void quicksort(int A[] int lo int hi) { //sorts A[lo] to A[hi] in ascending order int partition(int[] int int); if(lo < hi) { int dp = partition(A lo hi);//分的同时做了逐步细分的排序 quicksort(A lo dp-1);//区间迭代 quicksort(A dp 1 hi); } }

The call quicksort(num 1 n) will sort num[1..n] in ascending order.

We now look at how partition may be written. Consider the array:

We will partition it with respect to num[1] 53 (the pivot) by making one pass through the array. We will look at each number in turn. If it is bigger than the pivot we do nothing. If it is smaller we move it to the left side of the array.

Initially we set the variable lastSmall to 1; as the method proceeds lastSmall will be the index of the last item that is known to be smaller than the pivot. We partition num as follows:

1. Compare 12 with 53; it is smaller so add 1 to lastSmall (making it 2) and swap num[2] with itself.

2. Compare 98 with 53; it is bigger so move on.

3. Compare 63 with 53; it is bigger so move on.

4. Compare 18 with 53; it is smaller so add 1 to lastSmall (making it 3) and swap num[3] 98 with 18.

At this stage we have this:

5. Compare 32 with 53; it is smaller so add 1 to lastSmall (making it 4) and swap num[4] 63 with 32.

6. Compare 80 with 53; it is bigger so move on.

7. Compare 46 with 53; it is smaller so add 1 to lastSmall (making it 5) and swap num[5] 98 with 46.

At this stage we have the following:

8. Compare 72 with 53; it is bigger so move on.

9. Compare 21 with 53; it is smaller so add 1 to lastSmall (making it 6) and swap num[6] 63 with 21.

10. We have come to the end of the array; swap num[1] and num[lastSmall]; this moves the pivot into its final position.

We end up with this:

The division point is denoted by lastSmall (6).

We can express the previous procedure as a function partition.

#include <stdio.h> void quicksort(int A[] int lo int hi) { //sorts A[lo] to A[hi] in ascending order int partition(int[] int int); if(lo < hi) { int dp = partition(A lo hi); quicksort(A lo dp-1); // 相同子问题结构，递归调用partition(包括参数更新) quicksort(A dp 1 hi); // 相同子问题结构，递归调用partition(包括参数更新) } } int main() { void quicksort(int[] int int); int num[] = {0 53 12 98 63 18 32 80 46 72 21}; int n = 10; quicksort(num 1 n); for (int h = 1; h <= n; h ) printf("%d " num[h]); printf("\n"); getchar(); } int partition(int A[] int lo int hi) { //partition A[lo] to A[hi] using A[lo] as the pivot void swap(int[] int int); int pivot = A[lo]; int lastSmall = lo; for(int h = lo 1; h <= hi; h ) if(A[h] < pivot) { lastSmall; swap(A lastSmall h); } swap(A lo lastSmall); return lastSmall; //return the division point } void swap(int list[] int i int j) { //swap list[i] and list[j] int hold = list[i]; list[i] = list[j]; list[j] = hold; }

When run this produces the following output (num[1] to num[10] sorted):

12 18 21 32 46 53 63 72 80 98

Quicksort is one of those methods whose performance can range from very fast to very slow. Typically it is of order and for random data the number of comparisons varies between and . However things can get worse.

The idea behind partitioning is to break up the given portion into two fairly equal pieces. Whether this happens depends to a large extent on the value that is chosen as the pivot.

In the function we choose the first element as the pivot. This will work well in most cases especially for random data. However if the first element happens to be the smallest the partitioning operation becomes almost useless since the division point will simply be the first position. The “left” piece will be empty and the “right” piece will be only one element smaller than the given sublist. Similar remarks apply if the pivot is the largest element.

While the algorithm will still work it will be slowed considerably. For example if the given array is sorted quicksort will become as slow as selection sort.

One way to avoid this problem is to choose a random element as the pivot not merely the first one. While it is still possible that this method will choose the smallest (or the largest) that choice will be merely by chance.

Yet another method is to choose the median of the first (A[lo]) last (A[hi]) and middle (A[(lo hi)/2]) items as the pivot.

You are advised to experiment with various ways of choosing the pivot.

Our experiments showed that choosing a random element as the pivot was simple and effective even for sorted data.

In fact in many cases the method ran faster with sorted data than with random data an unusual result for quicksort.

One possible disadvantage of quicksort is that depending on the actual data being sorted the overhead of the recursive calls may be high. On the plus side quicksort uses very little extra storage. On the other hand mergesort (which is also recursive) needs extra storage (the same size as the array being sorted) to facilitate the merging of sorted pieces. Heapsort has neither of these disadvantages. It is not recursive and uses very little extra storage. And heapsort is stable in that its performance is always at worst regardless of the order of the items in the given array.

Another Way to Partition

There are many ways to achieve the goal of partitioning—splitting the list into two parts such that the elements in the left part are smaller than the elements in the right part. Our first method shown earlier placed the pivot in its final position. For variety we will look at another way to partition. While this method still partitions with respect to a pivot it does not place the pivot in its final sorted position. As we will see this is not a problem.

Consider again the array num[1..n] where n = 10.

We choose 53 as the pivot. The general idea is to scan from the right looking for a key that is smaller than or equal to the pivot. We then scan from the left for a key that is greater than or equal to the pivot. We swap these two values; this process effectively puts smaller values to the left and bigger values to the right.

We use two variables lo and hi to mark our positions on the left and right. Initially we set lo to 0 and hi to 11 (n 1). We then loop as follows:

1. Subtract 1 from hi (making it 10).

2. Compare num[hi] 21 with 53; it is smaller so stop scanning from the right with hi = 10.

3. Add 1 to lo (making it 1) .

4. Compare num[lo] 53 with 53; it is not smaller so stop scanning from the left with lo = 1.

5. lo (1) is less than hi (10) so swap num[lo] and num[hi] .

6. Subtract 1 from hi (making it 9).

7. Compare num[hi] 72 with 53; it is bigger so decrease hi (making it 8). Compare num[hi] 46 with 53; it is smaller so stop scanning from the right with hi = 8.

8. Add 1 to lo (making it 2).

9. Compare num[lo] 12 with 53; it is smaller so add 1 to lo (making it 3). Compare num[lo] 98 with 53; it is bigger so stop scanning from the left with lo = 3.

10. lo (3) is less than hi (8) so swap num[lo] and num[hi].

At this stage we have lo = 3 hi = 8 and num as follows:

11. Subtract 1 from hi (making it 7).

12. Compare num[hi] 80 with 53; it is bigger so decrease hi (making it 6). Compare num[hi] 32 with 53; it is smaller so stop scanning from the right with hi = 6.

13. Add 1 to lo (making it 4).

14. Compare num[lo] 63 with 53; it is bigger so stop scanning from the left with lo = 4.

15. lo (4) is less than hi (6) so swap num[lo] and num[hi] giving this:

16. Subtract 1 from hi (making it 5).

17. Compare num[hi] 18 with 53; it is smaller so stop scanning from the right with hi = 5.

18. Add 1 to lo (making it 5).

19. Compare num[lo] 18 with 53; it is smaller so add 1 to lo (making it 6). Compare num[lo] 63 with 53; it is bigger so stop scanning from the left with lo = 6.

20. lo (6) is not less than hi (5) so the algorithm ends.

The value of hi is such that the values in num[1..hi] are smaller than those in num[hi 1..n]. Here the values in num[1..5] are smaller than those in num[6..10]. Note that 53 is not in its final sorted position. However this is not a problem since to sort the array all we need to do is sort num[1..hi] and num[hi 1..n].

We can implement the procedure described above as partition2:

int partition2(int A[] int lo int hi) { //return dp such that A[lo..dp] <= A[dp 1..hi] void swap(int[] int int); int pivot = A[lo]; --lo; hi; while(lo < hi) { do --hi; while(A[hi] > pivot); do lo; while(A[lo] < pivot); if(lo < hi) swap(A lo hi); } return hi; } //end partition2

With this version of partition we can write quicksort2 as follows:

void quicksort2(int A[] int lo int hi) { //sorts A[lo] to A[hi] in ascending order int partition2(int[] int int); if(lo < hi) { int dp = partition2(A lo hi); quicksort2(A lo dp); quicksort2(A dp 1 hi); } } //end quicksort2

In partition2 we choose the first element as the pivot. However as discussed choosing a random element will give better results. We can do this with the following:

swap(A lo random(lo hi)); int pivot = A[lo];

where random can be written like this:

int random(int m int n) { //returns a random integer from m to n inclusive int offset = rand()/(RAND_MAX 1.0) * (n - m 1); return m offset; }

You are reminded to declare the prototype of random in partition2 and to add the following statement to your program since random uses rand and RAND_MAX:

#include <stdlib.h>

3 Nonrecursive Quicksort

In the versions of quicksort shown earlier after a sublist is partitioned we call quicksort with the left part followed by the right part. For most cases this will work fine. However it is possible that for a large n the number of pending recursive calls can get so large so as to generate a “recursive stack overflow” error.

In our experiments this occurred with n = 7000 if the given data was already sorted and the first element was chosen as the pivot. However there was no problem even for n = 100000 if a random element was chosen as the pivot.

Another approach is to write quicksort nonrecursively. This would require us to stack the pieces of the list that remain to be sorted. It can be shown that when a sublist is subdivided if we process the smaller sublist first the number of stack elements will be restricted to at most log2n.

For example suppose we are sorting A[1..99] and the first division point is 40. Assume we are using partition2 which does not put the pivot in its final sorted position. Thus we must sort A[1..40] and A[41..99] to complete the sort. We will stack (41 99) and deal with A[1..40] (the shorter sublist) first.

Suppose the division point for A[1..40] is 25. We will stack (1 25) and process A[26..40] first. At this stage we have two sublists—(41 99) and (1 25)—on the stack that remain to be sorted. Attempting to sort A[26..40] will cause another sublist to be added to the stack and so on. In our implementation we will also add the shorter sublist to the stack but this will be taken off immediately and processed.

The result mentioned above assures us that there will never be more than (rounded up) elements on the stack at any given time. Even for n = 1 000 000 we are guaranteed that the number of stack items will not exceed 20.

Of course we will have to manipulate the stack ourselves. Each stack element will consist of two integers (left and right say) meaning that the portion of the list from left to right remains to be sorted.

We define StackData and newStackData as follows:

typedef struct { int left right; } StackData;

StackData newStackData(int a int b) { StackData temp; temp.left = a; temp.right = b; return temp; }

We now write quicksort3 based on the above discussion.

#include <stdio.h> #include <stdlib.h> typedef struct { int left right; } StackData; StackData newStackData(int a int b) { StackData temp; temp.left = a; temp.right = b; return temp; } typedef struct node { StackData data; struct node *next; } Node *NodePtr; typedef struct stackType { NodePtr top; } StackType *Stack; Stack initStack() { Stack sp = (Stack) malloc(sizeof(StackType)); sp -> top = NULL; return sp; } int empty(Stack S) { return (S -> top == NULL); } void push(Stack S StackData data) { NodePtr np = (NodePtr) malloc(sizeof(Node)); np -> data = data; np -> next = S -> top; S -> top = np; } StackData pop(Stack S) { if (empty(S)){ printf("\nAttempt to pop an empty stack\n"); exit(1); } StackData hold = S -> top -> data; NodePtr temp = S -> top; S -> top = S -> top -> next; free(temp); return hold; } int random(int m int n) { //returns a random integer from m to n inclusive int offset = rand()/(RAND_MAX 1.0) * (n - m 1); return m offset; } void quicksort3(int A[] int lo int hi) { int partition2(int[] int int); Stack S = initStack(); push(S newStackData(lo hi)); int stackItems = 1 maxStackItems = 1; while(!empty(S)) { --stackItems; StackData d = pop(S); if(d.left < d.right) { //if the sublist is > 1 element int dp = partition2(A d.left d.right); if(dp - d.left 1 < d.right - dp) { //compare lengths of sublists push(S newStackData(dp 1 d.right)); push(S newStackData(d.left dp)); } else { push(S newStackData(d.left dp)); push(S newStackData(dp 1 d.right)); } stackItems = 2; //two items added to stack } if(stackItems > maxStackItems) maxStackItems = stackItems; } printf("Max stack items: %d\n\n" maxStackItems); } int main() { void quicksort(int[] int int); int num[] = {0 53 12 98 63 18 32 80 46 72 21}; int n = 10; quicksort3(num 1 n); for (int h = 1; h <= n; h ) printf("%d " num[h]); printf("\n"); getchar(); } int partition2(int A[] int lo int hi) { //return dp such that A[lo..dp] <= A[dp 1..hi] void swap(int[] int int); swap(A lo random(lo hi)); int pivot = A[lo]; --lo; hi; while(lo < hi) { do --hi; while(A[hi] > pivot); do lo; while(A[lo] < pivot); if(lo < hi) swap(A lo hi); } return hi; } void swap(int list[] int i int j) { //swap list[i] and list[j] int hold = list[i]; list[i] = list[j]; list[j] = hold; }

When partition2 returns the lengths of the two sublists are compared and the longer one is placed on the stack first followed by the shorter one. This ensures that the shorter one will be taken off first and processed before the longer one.

We also added statements to quicksort3 to keep track of the maximum number of items on the stack at any given time. When used to sort 100 000 integers the maximum number of stack items was 13; this is less than the maximum possible log2100000 = 17 rounded up.

As written even if a sublist consists of two items only the method will go through the whole process of calling partition checking the lengths of the sublists and stacking the two sublists. This seems an awful lot of work to sort two items.

We can make quicksort more efficient by using a simple method (insertion sort say) to sort sublists that are shorter than some predefined length (8 say). You are urged to write quicksort with this change and experiment with different values of the predefined length.

ref:

Noel Kalicharan 《Advanced Topics in C》

-End-