JavaAlgorithms
Elementary and no so elementary Java algorithms

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) 
MergeSort
Inmemory 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
<T>  A type that implements Comparable 
Definition at line 48 of file MergeSort.java.
void sort.MergeSort< T extends Comparable< T > >.m_sort  (  ArrayList< T >  vals, 
ArrayList< T >  temp,  
int  left,  
int  right  
)  [protected] 
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 mid1, and a right region that goes from mid to right.
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.
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.