# Doing a Merge Sort

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,```