Sorting using Recursion

One of the most elementary requirements in most programs is sorting. An array of numbers may need to be sorted in descending order, or a list of strings may need to be sorted in ascending order. Several of the popular sorting algorithms involve Recursion. Here are two of them.

Let's assume we need to sort a list of numbers in ascending order.

QuickSort

This algorithm is suitable for contiguous memory locations, i.e., it is suitable for Arrays, not linked lists. It involves selecting arbitrarily a number from the array, and partitioning the array into two. The left partition consists of numbers less than the selected number. The right partition consists of numbers greater than or equal to the selected number. The selected number is called a pivot.

Once the partitioning about the pivot is completed, the left-partition and right-parition are QuickSorted. This is the recursive definition of Quicksort.

So, Quicksort essentially consists of two parts - Partitioning and Sorting.

Sorting

The main (recursive) function would be something like the following:

QuickSort(left, right)
{
	int pivotpos;
	if (left < right)
	{
		pivotpos = Partition(left, right);
		QuickSort(left, pivotpos-1);
		QuickSort(right, pivotpos+1);
	}
}

Here, the function accepts the bounds of the part of the array to be sorted. Then, it calls the Partition function, which partitions that part of the array into two (as mentioned earlier) and returns the position of the pivot.

The position of the pivot need not be the center of the list. In fact, it is only in the ideal case that it resides in the center. The position of the pivot depends on its value. In the worst case, the pivot may be positioned at the start or at the end of the list.

The pivot position is used for defining the range for the next recursive call to QuickSort, as shown. First, the left partition is QuickSorted, then the right partition is. Recursion ends when left becomes greater than or equal to right.

Partitioning

The Partitioning algorithm has a substantial effect upon the speed of the QuickSort algorithm. The method described below is simple and fast.

First, a pivot is arbitrarily selected. To make the partitioning simpler, we shift the pivot to the start of the list, by swapping it with A[left].

We now sweep through the remaining elements (using a simple for loop) keeping the numbers less than the pivot to the left of the numbers greater than the pivot. We keep track of the position of the last "swept" number less than the pivot. Let this variable be 'last'. Let i be the for-loop variable, which is the index of th number currently being swept.

If A[i] is greater than or equal to the pivot, then nothing needs to be done. Simply increment i. This is because A[i] is already on the right side of the partition (right side of last).

If A[i] is less than the pivot, last is incremented, and A[i] is swapped with A[last]. This increases the size of the left partition, and places the smaller number in the left partition, and the larger number (first one of the right-partition) in the right-partition. Then, i is incremented.

In this way, we end with a list consisting of the pivot at the head, the small numbers in between, and the large numbers at the end. To complete the Partitioning, we place the pivot in between the two partitions by swapping it with A[last].

int Partition(int left, int right)
{
	int last, pivot, i;
	
	pivot=A[left];

	last=left;
	for (i=left+1; i<right; i++)
		if (A[i]>pivot)
		{
			last++;
			swap (A[last], A[i]);
		}

	swap (A[left], A[last]);
	return last;
}

Notice that I've arbitrarily selected A[left] as the pivot. It doesn't make a lot of difference, although it is generally better to select the pivot arbitrarily from the center of the list.

MergeSort

This algorithm performs, on average, less number of comparisons than QuickSort does. MergeSort is especially suitable for linked lists. When MergeSort is applied to sorting arrays, a lot of temporary memory space is required.

The main algorithm of MergeSort is fairly simple:

MergeSort(A)
{
	if (size(A)>1)
	{
		Divide(A, B);
		MergeSort(A);
		MergeSort(B);
		Merge(A, B, A);
	}
}

Here, A is a linked list to be sorted. MergeSort sorts this list by first dividing it into two equally-sized lists (A & B). It then MergeSorts these lists separately. Finally, the two sorted lists are merged together using a special Merge function.

The Divide( ) function simply divides the list. Any suitable algorithm may be used. The two lists should be same in size (or with a size difference of 1 at maximum.) One possible algorithm is to traverse the list with two pointers. One pointer should move at twice the speed of the other. When this pointer reaches the end, the slower pointer is at the middle. The list can be chopped at this point.

The Merge function takes the two sorted lists, and merges them in such a way that the resultant list is properly sorted. The following algorithm demonstrates the Merge function.

Merge(A, B, C)
{
	for (nodeA=startA, nodeB=startB; 
		nodeA || nodeB; )
		if (nodeA->no<nodeB->no)
		{
			Insert(nodeA->no, C);
			nodeA=nodeA->next;
		}
		else
		{	
			Insert(nodeB->no, C);
			nodeB=nodeB->next;
		}
}