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