com.mhhe.clrs2e
Class MergeSort

java.lang.Object
  |
  +--com.mhhe.clrs2e.MergeSort

All Implemented Interfaces:

Sorter

public class MergeSort

extends java.lang.Object

implements Sorter

Implements the Sorter interface via merge sort from pages 29 and 32 of Introduction to Algorithms, Second edition.

Constructor Summary

MergeSort()

Method Summary

private int	compare(java.lang.Comparable x, java.lang.Comparable y) Compares two objects, returning their relationship.
private void	merge(java.lang.Comparable[] array, int p, int q, int r) Merges two sorted subarrays array[p..q] and array[q+1..r].
private void	mergeSort(java.lang.Comparable[] array, int p, int r) Recursive merge sort procedure to sort the subarray array[p..r].
void	sort(java.lang.Comparable[] array) Sorts an array of Comparable objects.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MergeSort

public MergeSort()

Method Detail

sort

public void sort(java.lang.Comparable[] array)

Sorts an array of Comparable objects.

Specified by:

sort in interface Sorter

Parameters:

array - The array of Comparable objects to be sorted.

mergeSort

private void mergeSort(java.lang.Comparable[] array,
                       int p,
                       int r)

Recursive merge sort procedure to sort the subarray array[p..r].

Parameters:

array - The array containing the subarray to be sorted.

p - Index of the beginning of the subarray.

r - Index of the end of the subarray.

merge

private void merge(java.lang.Comparable[] array,
                   int p,
                   int q,
                   int r)

Merges two sorted subarrays array[p..q] and array[q+1..r]. Uses sentinels.

Parameters:

array - The array containing the subarrays to be merged.

p - Index of the beginning of the first subarray.

q - Index of the end of the first subarray; the second subarray starts at index q+1.

r - Index of the end of the second subarray.

compare

private int compare(java.lang.Comparable x,
                    java.lang.Comparable y)

Compares two objects, returning their relationship. If an object is given by a null reference, the object's value is assumed to be infinity.

Parameters:

x - One object.

y - The other object.

Returns:

A negative integer if x < y; 0 if x equals y; a positive integer if x > y.