2 Divide-and-Conquer
We use quicksort as an example for an algorithm that fol-
lows the divide-and-conquer paradigm. It has the repu-
tation of being the fasted comparison-based sorting algo-
rithm. Indeed it is very fast on the average but can be slow
for some input, unless precautions are taken.
The algorithm. Quicksort follows the general paradigm
of divide-and-conquer, which means it divides the un-
sorted array into two, it recurses on the two pieces, and it
finally combines the two sorted pieces to obtain the sorted
array. An interesting feature of quicksort is that the divide
step separates small from large items. As a consequence,
combining the sorted pieces happens automatically with-
out doing anything extra.
void QUICKSORT(int ℓ, r)
if ℓ < r then m = SPLIT(ℓ, r);
QUICKSORT(ℓ, m − 1);
QUICKSORT(m + 1, r)
endif.
We assume the items are stored in A[0..n − 1]. The array
is sorted by calling QUICKSORT(0, n − 1).
Splitting. The performance of quicksort depends heav-
ily on the performance of the split operation. The effect of
splitting from ℓ to r is:
• x = A[ℓ] is moved to its correct location at A[m];
• no item in A[ℓ..m − 1] is larger than x;
• no item in A[m + 1..r] is smaller than x.
Figure 1 illustrates the process with an example. The nine
items are split by moving a pointer i from left to right
and another pointer j from right to left. The process stops
when i and j cross. To get splitting right is a bit delicate,
in particular in special cases. Make sure the algorithm is
correct for (i) x is smallest item, (ii) x is largest item, (iii)
all items are the same.
int SPLIT(int ℓ, r)
x = A[ℓ]; i = ℓ; j = r + 1;
repeat repeat i++ until x ≤ A[i];
repeat j-- until x ≥ A[j];
if i < j then SWAP(i, j) endif
until i ≥ j;
SWAP(ℓ, j); return j.
i j
m
ji
1 9
3 5 4 2 41 92 7
5
7
4 2 9 4 2 17 3
3 5 4 2 4 2
Figure 1: First, i and j stop at items 9 and 1, which are then
swapped. Second, i and j cross and the pivot, 7, is swapped with
item 2.
Special cases (i) and (iii) are ok but case (ii) requires a
stopper at A[r + 1]. This stopper must be an item at least
as large as x. If r < n − 1 this stopper is automatically
given. For r = n −1, we create such a stopper by setting
A[n] = +∞.
Running time. The actions taken by quicksort can be
expressed using a binary tree: each (internal) node repre-
sents a call and displays the length of the subarray; see
Figure 2. The worst case occurs when A is already sorted.
Figure 2: The total amount of time is proportional to the sum
of lengths, which are the numbers of nodes in the corresponding
subtrees. In the displayed case this sum is 29.
In this case the tree degenerates to a list without branch-
ing. The sum of lengths can be described by the following
recurrence relation:
T (n) = n + T (n − 1) =
n
X
i=1
i =
n + 1
2
.
The running time in the worst case is therefore in O(n
2
).
In the best case the tree is completely balanced and the
sum of lengths is described by the recurrence relation
T (n) = n + 2 · T
n −1
2
.
5
