## Partition

Our only divide and conquer sorting algorithm so far is
mergesort. When we try mergesort with arrays we find that it
has the undesireable property of requiring us to allocate
additional memory. You see, if the "divide" step simply uses
two halves of the initial array as its smaller subproblems,
when we go to merge we won't have anyplace to put results as
we merge ... the sublists we're mergeing will be in the way.

So we thought about ways we might do the "divide" step of
a divide and conquer sorting method differently so as to be
able to sort "in place", i.e. without having to allocate
additional memory. We came to the conclusion that a
"divide" step that moved all the small values to the left
side of the array and all the large values to the right
would be perfect, since when the "conquer" step was over,
i.e. when the two halves had been sorted, there would be no
"merge" step - the array would already be sorted at that point.

The parition algorithm takes an array A, and range i..j in
that array, and a split value s, and moves around elements
of A in i..j so that everything less than s is on the left side,
and everything >= s is on the right side. Additionally, it
needs to tell us where the boundary between the "left" and
right "partitions" is, so it returns an index k, which is
the index of the last element in the left-hand partition.

Algorithm: partition(A,i,j,s)
Inputs: A, an array,
i ≤ j, integers defining a range A[i],..,A[j] in A
s, a value from A[i],...,A[j]
Side Effects: The elements of A[i],...,A[j] may be reordered
Output: k such that A[i],...,A[k] all < s, A[k+1],...,A[j] all ≥ s
k ← partition(A,i,j,s)
{
while(true)
{
while (j ≥ i && A[j] ≥ s)
j--;
while (A[i] < s)
i++;
if (i < j)
swap(A[i],A[j]);
else
return j;
}
}

Without thinking too hard, you should see that this is a
Θ(n) algorithm, where n is the size of the array range
i..j. At least if we assume that swapping and comparing
elements of A takes constant time.

## Quicksort

Using partition, we get a new divide an conquer sorting
algorithm called quicksort. The idea is pretty simple: use
partition to split the array into two ranges, recursively sort
each range and then you're done. The only problem is this:
what should we use for a split value? The mose basic
quicksort algorithm simply uses the first element in the range
as a split value, i.e. A[i]. The idea is that if the input is
random, the first element is just as likely to be a good split
value as any other.

So quicksort is

quicksort(A,i,j)
1) call partition on A and the range i..j using the first element of the range as the split value
**Important:** Deal with empty partition as per class discussion!
2) recursively sort the left range
3) recursively sort the right range

In the best case, our split value will always partition the
array into two equal sized pieces.
This gives a recurrence
relation of

T(n) = 2 T(n/2) + Θ(n)

where n is the size of the range we're sorting.
We've seen before that this is
T

_{B}(n) = Θ(n lg n).
In the worst case, our split value will always partition the
array into pieces of size 1 and n-1.
This gives a recurrence
relation of

T(n) = T(n-1) + Θ(n)

where n is the size of the range we're sorting. As we
discussed in class,
we simply apply the recurrence over and over until we see a
pattern and deduce that T

_{W}(n) = Θ(n^2).