package Algorithm;
public class MergeSort2 {
// merge sorted array a and b into c
static void mergeArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m){
c[k++]= a[i]<b[j]?a[i++]:b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
static void sortArray(int a[],int n,int sorted[]){
System.out.println("n="+n);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("++++++");
int mid = n/2;
if(n==1){
sorted[0] = a[0];
return;
}
if(n>1){
int[] left = new int[mid];
int[] right = new int[n-mid];
int j = 0; // the point of a array
for(int i=0;i<left.length;i++){
left[i] = a[j++];
}
for(int i=0;i<right.length;i++){
right[i] = a[j++];
}
int []leftSorted = new int[left.length];
sortArray(left,left.length,leftSorted);
int []rightSorted = new int[right.length];
sortArray(right,right.length,rightSorted);
mergeArray(left, left.length, right, right.length,sorted);
}
System.out.println("after sort");
for(int i=0;i<n;i++){
System.out.print(sorted[i]+" ");
}
}
public static void main(String[] args) {
int[] a = new int[]{4,7,10,13,18,3,5,9,11,19,21};
// int[] a = new int[]{4};
int[] sorted = new int[a.length];
sortArray(a,a.length,sorted);
for (int i = 0; i < sorted.length; ++i) {
System.out.print(sorted[i] + " ");
}
}
}
Result:
n=11
4 7 10 13 18 3 5 9 11 19 21 ++++++
n=5
4 7 10 13 18 ++++++
n=2
4 7 ++++++
n=1
4 ++++++
n=1
7 ++++++
after sort
4 7 n=3
10 13 18 ++++++
n=1
10 ++++++
n=2
13 18 ++++++
n=1
13 ++++++
n=1
18 ++++++
after sort
13 18 after sort
10 13 18 after sort
4 7 10 13 18 n=6
3 5 9 11 19 21 ++++++
n=3
3 5 9 ++++++
n=1
3 ++++++
n=2
5 9 ++++++
n=1
5 ++++++
n=1
9 ++++++
after sort
5 9 after sort
3 5 9 n=3
11 19 21 ++++++
n=1
11 ++++++
n=2
19 21 ++++++
n=1
19 ++++++
n=1
21 ++++++
after sort
19 21 after sort
11 19 21 after sort
3 5 9 11 19 21 after sort
3 4 5 7 9 10 11 13 18 19 21 3 4 5 7 9 10 11 13 18 19 21
No comments:
Post a Comment