In the previous article, we introduced the concept of modules and functions, and even created a simple Python program to test for palindromes. In this article, we will continue our look at recursion and put some of the concepts introduced in previous articles into practice by coding the merge sort algorithm in Python.

For this article, we need to introduce the concept of a sorting algorithm. A common problem in computer science is the need to sort a list of items. A sorting algorithm is an algorithm that puts elements of a list into order. The most-used orders are numerical order and lexicographical order. But sorting a list efficiently has been problematic. Early search algorithms increased exponentially with the size of the list. They were on an order of n squared; that is, if the number of list items doubled, the number of list operations increased fourfold; if the list size quadrupled, the number of list operations increased sixteen-fold, and so on.

One of the simplest sort algorithms consists of simply going through a list of unsorted items sequentially, comparing the item to all remaining items, and swapping items that are out of place. We start at the first item, and compare the item to all other items, swapping the first item with the item to which we are comparing it when necessary. Once we have reached the end of the list, we know the first item of the list has the lowest value of any item on the list, and we can move on to the second item. We keep going, updating the list pointer, until we reach the end of the list. This is called a selection sort, and it is simple to implement:

def selectionSort(L):
	'''Implement a simple selection sort:
        (Not as effecient as merge sort)
	Compare each element with each subsequent
	item on the list; if they are out of place,
	swap them; keep going until we rech the end 
	of the list'''
	for i in range(0,len(L)-1):
		for j in range(i+1,len(L)):
			# If items out of place, switch
			if L[i] > L[j]:
				temp = L[i]
				L[i] = L[j]
				L[j] = temp

In this function, we have two for loops, one nested inside the other one. If the lower-indexed list member is greater than the higher-indexed one, we swap them. Although this will work, you can see the problem with selection sorts. For a list of n items, for each item, we must carry out as many comparisons as the current list position minus one. For the first list item, we have n-1 comparisons; for the second list item, n-2, and so on. There is an average of n/2 comparisons for each item, and we make n-1 passes through the list. That leaves us with (n^2-n)/2 operations. Dropping out lower terms, this means the bubble sort is on the order of O(n^2). This is far from ideal, and generally bubble sorts are only acceptable for relatively small lists.

Merge Sort: An Efficient Sorting Algorithm

One possible alternative is the merge sort algorithm. Merge sort works as follows:

1. Divide the list into two equally-sized sublists.
2. Apply the merge sort algorithm recursively on the sublists.
3. Merge the two sorted lists.

Recursion requires a base case, and in merge sort, the base case is a list size of 1. In this case, the list is already sorted. On all other levels of recursion we have to merge the sorted lists. Merging the lists requires us to move through each list, placing each item into a temporary location. At each level where there is a merge operation taking place, a total of n operations are carried out. Since we are halfing the lists at each level of recursion, however, there are only log(n) levels. To confirm this is the case, let us consider the case where there are 8 items on the list:

• First level: Divide the list into two lists of four.
• Second level: Divide the two lists of four into four lists of two.
• Third level: Divide the lists in half – we have reached the base case. Merge together the lists of one. There are eight lists of one to merge into four lists of two, so there are 8*1 = 8 operations.
• Second level: Merge the four lists of two into two lists of four. There are four lists of two, so there are 4*2 = 8 operations.
• First level: Merge the two lists of four into a single list. There are two lists of four, so there are 8 operations.

For a list of 8 items, there are 4 levels of recursion, but the fourth level is the base case, so there are 3 levels at which a merge is performed. Doubling the size of the list would add another level of recursion. Thus, the number of levels is log(n). Multiply that by the number of operations at each level and we get n log(n) operations.

This is an improvement over the selection sort, so it may be worth implementing. The pseudocode for the merge sort function is relatively easy to write:

mergesort(mylist,low,high):
if low < high
mergesort(mylist,low,low+(high-low)/2)
mergesort(mylist,low+((high-low)/2)+1,high)
merge lists into temporary location
copy merged list into mylist

As we apply the merge sort function recursively, eventually low equals high, ending the recursion. The actual Python function is slightly harder to code, but not by much:

def mergeSort(L,low=int(0),high=int(-1)):
    # Implementation of the merge sort algorithm
    # If high has default value, set it to len(L)-1
    # (index of last item on the list)
    if high == -1:
        high = len(L)-1
    if low < high:
	# Apply mergeSort on each half of the list
        mergeSort(L,low,int((low+(high-low)/2)))
        mergeSort(L,low+int(((high-low)/2))+1,high)
	# Now, merge the lists in temporary location
        i = low
        j = low+int(((high-low)/2))+1
        lb = j
        k = 0
        temp = []
        while k <= high-low:
            if i < lb and j <= high and L[i] > L[j]:
                temp.append(L[j])
                j = j + 1
            elif i < lb and j <= high and L[i] <= L [j]:  
                temp.append(L[i])                       
                i = i + 1             
            elif j > high:
                temp.append(L[i])
                i = i + 1
            elif i >= lb:
                temp.append(L[j])
                j = j + 1
            k = k + 1
        # Copy the list to its original location
        j = 0
        for i in range(low,high+1):
            L[i] = temp[j]
            j = j + 1

Our mergeSort function takes three arguments: the list itself and the lower and upper indices, indicating which subset of the list to sort. I wanted to be able to call the function with just one parameter (the list) in cases where I wanted to sort the entire list, so I added default values for low and high: the default value for low should be 0 obviously, but the value for high depends on the size of the list. Since we can’t use len(L)-1 as the default value for high (since L is itself a formal parameter), I used -1 as the default value for high since it is obviously out of bounds. If high is -1, we set it to len(L)-1. It’s a kludge, but it serves its purpose.

Next, we check to see if low is less than high. If they are equal, we have reached a base case. If not, then we call the merge sort function recursively on each half of the list. When we are done, we merge the two lists. Merging the lists entails the following:

1. Create a temporary list to store the merged list.
2. Create and initialize indices for both lists (i and j in our example).
3. Compare L[i] to L[j]. Place the smaller item into the temporary list.
4. Increment the index for the list whose item was put in the temporary list.
5. If the end of either list has not been reached, go back to [3].
6. Place any remaining list items in the temporary list.
7. Copy the temporary list into L.

One of the drawbacks of merge sort is that you have to allocate temporary space to initially store the merged lists. One possible alternative is a binary heap, which we will examine in the next article.

The merge sort source code is available here.

External Links:

Sorting algorithm at Wikipedia

Merge sort at Wikipedia