public class MergeSort {
public int A[], temp[]; //, size=0;
MergeSort(int n) {
A = new int[n];
temp = new int[n];
//size = n;
}
MergeSort() {
A = null;
temp = null;
//size = 0;
}
public void mergeSort(int A[], int left, int right) {
int mid;
//System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
if (left < right) {
mid = (right + left) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
}
public void merge(int A[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L1[] = new int[n1];
int L2[] = new int[n2];
for (int i = 0; i < n1; i++) {
L1[i] = A[left + i];
}
for (int i = 0; i < n2; i++) {
L2[i] = A[mid + i + 1];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L1[i] <= L2[j]) {
A[k] = L1[i];
i++;
} else {
A[k] = L2[j];
j++;
}
k++;
}
while (i < n1) {
A[k] = L1[i];
i++;
k++;
}
while (j < n2) {
A[k] = L2[j];
j++;
k++;
}
}
public void printArr() {
System.out.print("Sorted: ");
for (int i = 0; i < this.A.length; i++) {
System.out.print(this.A[i] + ", ");
}
System.out.println();
}
public static void main(String args[]) {
MergeSort sort = new MergeSort();
sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
sort.temp = new int[8];
sort.mergeSort(sort.A, 0, 7);
// print sorted Array
sort.printArr();
}
}
public int A[], temp[]; //, size=0;
MergeSort(int n) {
A = new int[n];
temp = new int[n];
//size = n;
}
MergeSort() {
A = null;
temp = null;
//size = 0;
}
public void mergeSort(int A[], int left, int right) {
int mid;
//System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
if (left < right) {
mid = (right + left) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
}
public void merge(int A[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L1[] = new int[n1];
int L2[] = new int[n2];
for (int i = 0; i < n1; i++) {
L1[i] = A[left + i];
}
for (int i = 0; i < n2; i++) {
L2[i] = A[mid + i + 1];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L1[i] <= L2[j]) {
A[k] = L1[i];
i++;
} else {
A[k] = L2[j];
j++;
}
k++;
}
while (i < n1) {
A[k] = L1[i];
i++;
k++;
}
while (j < n2) {
A[k] = L2[j];
j++;
k++;
}
}
public void printArr() {
System.out.print("Sorted: ");
for (int i = 0; i < this.A.length; i++) {
System.out.print(this.A[i] + ", ");
}
System.out.println();
}
public static void main(String args[]) {
MergeSort sort = new MergeSort();
sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
sort.temp = new int[8];
sort.mergeSort(sort.A, 0, 7);
// print sorted Array
sort.printArr();
}
}
No comments:
Post a Comment