Recursive Sorting Algorithms

General purpose sorts which achieve better efficiency than purely iterative algorithms (e.g. selection sort, bubble sort, exchange sort) exist. These use recursive algorithms. A recursive algorithm calls itself.

Examples: merge sort, quick sort.

Efficiency: O Nlog₂N moves and comparisons. Quick sort is a bit faster and more memory efficient, but it is slightly harder to describe.

Merge Sort

Illustration

Try this algorithm with a pack of cards. First decide the sort order, e.g bridge rules (i.e. aces high with suit precendence: clubs, diamonds, hearts, spades). Then sort the pack by splitting it in 2, sorting each half and merging the 2 half packs into a sorted pack. When sorting half, quarter or smaller packs the same algorithm (approach) can be used. Of course a pack containing only 1 card is already sorted.

Sort algorithm

Parameters: address of array, starting and ending indexes.

IF start_index == end_index :
	return  // Only 1 record so block is already sorted
mid_index = (start_index + end_index)/2
	// integer division, no fraction
// sort lower half
sort(array_address, start_index, mid_index)
// sort upper half
sort(array_address, mid_index+1, end_index)
// merge lower and upper half blocks into sorted block
merge(array_address,low_index,mid_index,high_index)

Merge algorithm

Parameters: address of array, starting, mid and ending indexes.

Declare static local array for merging into
WHILE items exist to be merged from both halves:
	IF next item in lowerhalf lower than next item in upper half:
		copy item from lower half into local array
	ELSE:
		copy item from upper half into local array
FOR all items not yet copied in either half:
	copy item into local array
FOR all items in local array:
	copy item back into original block

Quick Sort

This algorithm is the fastest general-purpose sort known. Faster sorts are possible for data whose key values make it is feasible to use a hash-table sort.

Description

The same approach (i.e. immediate return) is taken as by merge sort for record blocks sizes of less than 2 which are already sorted. Quick sort otherwise works by selecting an arbitrary record (e.g. the first) and counting how many records in the block come below this value (let's call this number of records X). The arbitrary record is then swapped with the (X+1)th record. This partitions the original block into 3:

a. The bottom part from the first to the Xth record inclusive.
b. The middle part being the (X+1)th record (now in its final sorted position).
c. The top part being from the (X+2)th record to the last record inclusive.

There should now be the same number of records in the bottom part which will need to be moved into the top part as vice-versa. The next part of the algorithm involves swapping these records between bottom and top parts. This is achieved using 2 indexes used to search through the top part (starting at the top record, going down by 1 each search) and the bottom part (starting at the bottom record going up by 1 each search), finding the next pair of records to swap into the correct parts, until either index gets to the middle record, the (X+1)th position.

All the records in the bottom part are now lower in the sort order than the record in the middle part, which is lower than all the records in the top part of the original block.

The sort algorithm is next applied recursively to the bottom part and to the top part. The middle record is correctly positioned so it doesn't need to be moved.

There is no reason why the bottom and top parts should be equal in size. It is also as likely that one part will have zero size as any other possible size . Due to the arbitrary selection of the record to be swapped into the (X+1)th position, there will be a near enough to 50/50 split often enough on average to make this algorithm efficient. Also, even if occasionally the top or bottom part might have 0 records, this doesn't prevent this algorithm from resolving because the block is still split between the other part and the middle record.

Quick Sort Algorithm

parameters: address of array, indexes of bottom and top records in part of array to be sorted.

// handle trivial case
IF 1 or fewer records:
	return
// find correct position for start record:
X=0
FOR all records from start +1 to end:
	IF record higher than start:
		X=X+1
Swap start and (X+1)th records

// swap records in wrong part for each other 
bot_index=start
top_index=end
DO :
	WHILE record at top_index in correct part and top_index > X+1:
		top_index = top_index-1

	WHILE record at bot_index in correct part and bot_index < X+1:
		bot_index = bot_index +1
	IF top_index > X+1 and bot_index < X+1:
		swap records at top_index and bot_index
WHILE bot_index != X+1 AND top_index != X+1;

// sort bottom and top parts
sort(array,start,X)
sort(array,X+2,end)