sort.MergeSort< T extends Comparable< T > > Class Reference

List of all members.

Public Member Functions
void	mergeSort (ArrayList< T > vals)
Protected Member Functions
void	merge (ArrayList< T > vals, ArrayList< T > temp, int left, int mid, int right)
void	m_sort (ArrayList< T > vals, ArrayList< T > temp, int left, int right)

---

Detailed Description

MergeSort

In-memory merge sort.

For N elements, the merge sort uses approximately 2N elements. The time complexity is order N(log2(N)).

The merge sort code is implemented as a Java generic, so it can be used to support any array that consists of objects that implement the Comparable interface.

This merge sort algorithm is modeled after an algorithm, implemented in C, published on Prof. Rashid Bin Muhammad on his web site: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm.

May 31, 2013

Author:

Ian Kaplan, iank@bearcave.com

Parameters:

<T>	A type that implements Comparable

Definition at line 48 of file MergeSort.java.

---

Member Function Documentation

void sort.MergeSort< T extends Comparable< T > >.m_sort	(	ArrayList< T >	vals,
		ArrayList< T >	temp,
		int	left,
		int	right
	)		[protected]

Parameters:

vals	the values to be sorted
temp	temporary storage (the same size as the vals array)
left	the lower array index for the region to be sorted
right	the upper index for the region to be sorted.

Definition at line 116 of file MergeSort.java.

void sort.MergeSort< T extends Comparable< T > >.merge	(	ArrayList< T >	vals,
		ArrayList< T >	temp,
		int	left,
		int	mid,
		int	right
	)		[protected]

Merge two sorted regions. There is a left region that goes from left to mid-1, and a right region that goes from mid to right.

Parameters:

vals	the values array containing the sorted regions
temp	temporary storage, which is the same size as the vals array
left	the lower array index of the "left" region
mid	the middle, which divides the two regions to be merged
right	the upper array index for the "right" region.

Definition at line 65 of file MergeSort.java.

void sort.MergeSort< T extends Comparable< T > >.mergeSort

(

ArrayList< T >

vals

)

Use merge sort to sort an array of values.

The values are passed in the the vals array argument and the sorted values are returned in the same array.

Parameters:

vals	the values to be sorted
temp	temporary storage, which must be the same size as the vals array.

Definition at line 140 of file MergeSort.java.

---

The documentation for this class was generated from the following file:

• sort/MergeSort.java