package Sorts; /** * * Merge Sort *
* The basic idea for merge sorting a list, such as (5,3,8,6,7,2,4,1), is a three-step process: *
* 1) divide the list in two halves, L = (5,3,8,6) and R = (7,2,4,1); *
* 2) sort the two half-lists, getting L = (3,5,6,8) and R = (1,2,4,7); and *
* 3) merge the two half-lists into the final sorted list Merge(L,R)=(1,2,3,4,5,6,7,8).
*
* @author wilsonsoto
* @since 20.09.15
*
*/
public class MergeSort {
/**
*
* @param a Comparable[]
* @param left int
* @param right int
*
*/
public static void mergeSort(Comparable[] a, int left, int right) {
if (left < right) {
Comparable[] b = new Comparable[a.length];
int middle = (left + right) / 2;
mergeSort(a, left, middle);
mergeSort(a, middle + 1, right);
merge(a, b, left, middle, right); // merge a to b
copy(b, a, left, right); // copy result back to a
}
}
/**
*
* @param b Comparable[]
* @param a Comparable[]
* @param i int
* @param j int
*
*/
public static void copy (Comparable[] b, Comparable[] a, int i, int j) {
for (int idx=i; idx<=j; idx++)
a[idx] = b[idx];
}
/**
*
* @param a Comparable[]
*
*/
public static void mergeSort(Comparable[] a) {
Comparable[] b = new Comparable[a.length];
int segmentSize = 1;
while (segmentSize < a.length) {
mergePass(a, b, segmentSize); // merge from a to b
segmentSize += segmentSize;
//System.out.print(segmentSize+":");
//for (int i=0;i