Advanced Topics in C: Core Concepts in Data Structures by Noel Kalicharan

Author:Noel Kalicharan [Kalicharan, Noel]
Language: eng
Format: epub, pdf
ISBN: 9781430264002
Publisher: Apress
Published: 2013-10-31T04:00:00+00:00

6.7 Merge Sort

Consider, again, the problem of sorting a list of n items in ascending order. We will illustrate our ideas with a list of integers. In Section 1.8, we saw how to merge two sorted lists by traversing each list once. We now show how to use recursion and merging to sort a list. Consider this:

sort a list

sort first half of list

sort second half of list

merge sorted halves into one sorted list

end sort

Clearly, if we can sort the two halves and then merge them, we will have a sorted list. But how do we sort the halves? We use the same method! Here’s an example:

sort first half of list

sort first half of first half of list (one quarter of the original list)

sort second half of first half of list (one quarter of the original list)

merge sorted halves into one sorted list

end sort

For each piece we have to sort, we break it into halves, sort the halves, and merge them. When do we stop using this process on a piece? When the piece consists of one element only, there is nothing to do to sort one element. We can modify our algorithm as follows:

sort a list

if the list contains more than one element then

sort first half of list

sort second half of list

merge sorted halves into one sorted list

end if

end sort

We assume the list is stored in an array, A, from A[lo] to A[hi]. We can code the algorithm as a C function as follows:

void mergeSort(int A[], int lo, int hi) {

void merge(int[], int, int, int);

if (lo < hi) { //list contains at least 2 elements

int mid = (lo + hi) / 2; //get the mid-point subscript

mergeSort(A, lo, mid); //sort first half

mergeSort(A, mid + 1, hi); //sort second half

merge(A, lo, mid, hi); //merge sorted halves

}

}

This assumes that merge is available and the following statement will merge the sorted pieces in A[lo..mid] and A[mid+1..hi] so that A[lo..hi] is sorted:

merge(A, lo, mid, hi);

We will show how to write merge shortly.

But first, we show how this function sorts the following list stored in an array, num:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.