The code below uses Merge Sort to sort an array of integers
public class MergeSort {
private int []mArray;
private int []mTemp;
public MergeSort(int []arr) {
mTemp = new int[arr.length];
mArray = arr;
divide(0, arr.length-1);
System.out.println("Final list");
for(int i: mArray) {
System.out.print(i +",");
}
System.out.println("");
}
private void divide(int low, int high) {
System.out.println("divide() - " + low +"," + high);
if (low < high) {
int mid = low + ((high-low)/2);
System.out.println("mid=" + mid);
divide(low, mid);
divide(mid+1, high);
join(low, mid, high);
}
}
private void join(int low, int mid, int high) {
System.out.println("join() - " + low + "," + mid + "," + high);
//copy all values to temp array
for(int i =low; i <= high; i++) {
mTemp[i] = mArray[i];
System.out.print(mTemp[i] + ",");
}
System.out.println("");
//divide array into two parts from mid point
int leftCounter = low;
int rightCounter = mid+1;
int mainCounter = low;
//compare number in left side to number in right side.
// Move lower number to the main array
while (leftCounter <= mid && rightCounter <= high) {
System.out.println("comparing " + mTemp[leftCounter] + " to " + mTemp[rightCounter]);
if (mTemp[leftCounter] <= mTemp[rightCounter]) {
mArray[mainCounter] = mTemp[leftCounter];
leftCounter++;
} else {
mArray[mainCounter] = mTemp[rightCounter];
rightCounter ++;
}
mainCounter ++;
}
System.out.println("Appending remaining numbers from left side");
//append remaining numbers in left side to main array
while (leftCounter <= mid) {
mArray[mainCounter] = mTemp[leftCounter];
System.out.println(mArray[mainCounter]);
leftCounter ++;
mainCounter ++;
}
System.out.println("At end of join()");
for(int i =low; i <= high; i++) {
System.out.print(mArray[i] + ",");
}
System.out.println("");
}
public static void main(String []args) {
int [] nums = {6,78,19,54,32,-9,-10,87,12,31};
for(int i: nums) {
System.out.print(i +",");
}
System.out.println("");
MergeSort m = new MergeSort(nums);
}
}
The output is shown below
6,78,19,54,32,-9,-10,87,12,31, divide() - 0,9 mid=4 divide() - 0,4 mid=2 divide() - 0,2 mid=1 divide() - 0,1 mid=0 divide() - 0,0 divide() - 1,1 join() - 0,0,1 6,78, comparing 6 to 78 Appending remaining numbers from left side At end of join() 6,78, divide() - 2,2 join() - 0,1,2 6,78,19, comparing 6 to 19 comparing 78 to 19 Appending remaining numbers from left side 78 At end of join() 6,19,78, divide() - 3,4 mid=3 divide() - 3,3 divide() - 4,4 join() - 3,3,4 54,32, comparing 54 to 32 Appending remaining numbers from left side 54 At end of join() 32,54, join() - 0,2,4 6,19,78,32,54, comparing 6 to 32 comparing 19 to 32 comparing 78 to 32 comparing 78 to 54 Appending remaining numbers from left side 78 At end of join() 6,19,32,54,78, divide() - 5,9 mid=7 divide() - 5,7 mid=6 divide() - 5,6 mid=5 divide() - 5,5 divide() - 6,6 join() - 5,5,6 -9,-10, comparing -9 to -10 Appending remaining numbers from left side -9 At end of join() -10,-9, divide() - 7,7 join() - 5,6,7 -10,-9,87, comparing -10 to 87 comparing -9 to 87 Appending remaining numbers from left side At end of join() -10,-9,87, divide() - 8,9 mid=8 divide() - 8,8 divide() - 9,9 join() - 8,8,9 12,31, comparing 12 to 31 Appending remaining numbers from left side At end of join() 12,31, join() - 5,7,9 -10,-9,87,12,31, comparing -10 to 12 comparing -9 to 12 comparing 87 to 12 comparing 87 to 31 Appending remaining numbers from left side 87 At end of join() -10,-9,12,31,87, join() - 0,4,9 6,19,32,54,78,-10,-9,12,31,87, comparing 6 to -10 comparing 6 to -9 comparing 6 to 12 comparing 19 to 12 comparing 19 to 31 comparing 32 to 31 comparing 32 to 87 comparing 54 to 87 comparing 78 to 87 Appending remaining numbers from left side At end of join() -10,-9,6,12,19,31,32,54,78,87, Final list -10,-9,6,12,19,31,32,54,78,87,
Leave a Reply