MergeSort

package harry.algorithms;

import org.junit.Test;

import java.util.Arrays;

/**

 * User: Xu.hai

 * Date: 11-8-10

 * Time: 上午10:12

 * To change this template use File | Settings | File Templates.

 */

public class MergeSort {

public void merge(int A[],int p, int q, int r) {

int n1=q-p+1;

int n2=r-q;

int L[] = new int[n1+1];

int R[] = new int[n2+1];

int i=0,j=0;

for (;i<n1;i++) {

L[i] = A[p+i];

}

for (;j<n2;j++) {

R[j] = A[q+j+1];

}

L[n1] = Integer.MAX_VALUE;

R[n2] = Integer.MAX_VALUE;

i=j=0;

for (int k=p;k<=r;k++) {

if (L[i]<R[j]) {

A[k] = L[i];

i++;

} else {

A[k]=R[j];

j++;

}

}

}

public void mergeSort(int A[],int p,int r){

if (p<r) {

int q=(p+r)/2;

mergeSort(A, p, q);

mergeSort(A, q+1, r);

merge(A, p, q, r);

}

}

@Test

public void tt(){

int A[] = {5,4,2,7,3,1,2,6};

mergeSort(A,0,3);

System.out.println(Arrays.toString(A));

}

}