Describe the sort pattern. Discuss the quick sort routines in terms of this pattern.

What will be an ideal response?

Sort array
1)Get split point and Split two parts
2)Sort first part(recursive)
3)Sort second part (recursive)
4)Join sorted parts.

Quick sort:
1)Split into what we hope are roughly equal parts,
this may not be the case.
Postcondition on the split: Each element in upper
half is >= each element in the lower half. The hard
work is done here.
2)Recursively sort the first part
3)Recursively sort the second part
4)The join is trivial
The division into two pieces of nearly equal size will cause the routine to run in N log N time, that is, O(N log N) time. There is a non-negligible probability that the arrays will consistently be of size 1 and size N-1 respectively, which will result in O(N2) run time