Merge Sort
An Introduction with Examples |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
mergesort(a[]) { if (a has two or more elements) { mergesort(left half of a); mergesort(right half of a); merge(left and right halves of a); } }
Sorting the six-element array (8, 4, 7, 3, 9, 3)
mergesort
and one
call to merge
mergesort
has worst case
efficiency of \(T(n/2)\)merge
has worst case efficiency of
\(n\) (to merge the two half arrays)/** * Merges two halves of a subarray. * * Side Effects: The arrays is sorted in place * * @param a The array containing the subarray * @param first The index of the first element of the subarray * @param last The index of the last element of the subarray */ void merge(int a[], int first, int last) { int i, j, k, middle, n, start, stop; int *temp; if (first >= last) return; // Allocate temporary storage temp = new int[last - first + 1]; // Divide the subarray in half middle = (first + last) / 2; i = 0; j = first; k = middle + 1; // Put the elements of the halves (which are assumed to be // sorted) in temp in the proper order while ((j <= middle) && (k <= last)) { if (a[j] < a[k]) { temp[i] = a[j]; i++; j++; } else { temp[i] = a[k]; i++; k++; } } // Since the two halves may not be the same size we need to // copy the remaining elements of the subarray into temp while (j <= middle) { temp[i] = a[j]; i++; j++; } while (k <= last) { temp[i] = a[k]; i++; k++; } // Copy the elements of temp into the subarray for (i = first; i <= last; i++) { a[i] = temp[i - first]; } // Deallocate the temporary storage // delete[] temp; } /** * Does the actual work of the merge sort * * @param a The array of integers * @param first The index of the first element of the subarray * @param last The index of the last element of the subarray * * @effects The order of the elements in a is changed */ void mergesort(int a[], int first, int last) { int middle; if (first < last) { middle = (first + last) / 2; mergesort(a, first, middle); mergesort(a, middle + 1, last); merge(a, first, last); } } /** * Sort an array of integers using a merge sort * * The array is sorted "in place" * * @param a The array of integers * @param length The number of elements in the array * * @effects The order of the elements in a is changed */ void sort(int a[], int length) { mergesort(a, 0, length - 1); }