Recursive Sorts: An Overview

General Divide-and-Conquer Sorting

Name: SortByDivideAndConquer
Input: A sequence, called s, and two positions in that sequence, called firstPosition and lastPosition, with firstPosition <= lastPosition
Output: s has been sorted into ascending order from firstPosition to lastPosition, inclusive

Algorithm SortByDivideAndConquer(s, firstPosition, lastPosition)
------------------------------------------------------------------------------
Split sequence s from firstPosition to lastPosition (inclusive) into two parts
Sort1 the first part
Sort2 the second part
Combine the two sorted parts into one sorted sequence

Recursive Divide-and-Conquer Sorting

Name: SortRecursively
Input: A sequence, called s, and two positions in that sequence, called firstPosition and lastPosition, with firstPosition <= lastPosition
Output: s has been sorted into ascending order from firstPosition to lastPosition, inclusive

Algorithm SortRecursively(s, firstPosition, lastPosition)
------------------------------------------------------------------------------
Split sequence s from firstPosition to lastPosition (inclusive) into two parts
SortRecursively the first part
SortRecursively the second part
Combine the two sorted parts into one sorted sequence

Questions arising from the recursive divide-and-conquer sorting pseudocode

Three obvious questions arising from the above pseudocode are these:

1. How do we split the incoming sequence into two parts?
2. How do we sort the two sub-sequences?
3. How do we combine the sorted sub-sequences to obtain a sorted version of the original sequence?

The short answer is that by choosing different ways to split the sequence into sub-sequences, and then later combining the sorted sub-sequences to get the original sequence in sorted form, we can obtain several very different algorithms for performing the overall sort, including the well-known MergeSort and QuickSort.

One thing to note is this: To keep the pseudocode simple, we have only split the sequence into two sub-sequences, but in fact there is no reason why we could not split it into more than two.

And here's a second thing to note: The names of the sorting procedures for the sub-sequences in the first case above (Sort1 and Sort2, in the general divide-and-conquer situation), are meant to suggest that the two procedures could be entirely different for each sub-sequence. In the recursive divide-and-conquer, by contrast, the procedure applied to each sub-sequence is exactly the same as that applied to the original sequence, a situation implied by the names being the same. This is to be expected, of course, when the algorithm is a recursive one.