Merge Sort - Java Code

A stable, comparison based,  divide and conquer sorting algorithm

• Worst case time complexity: O(n log n)
• Best case time complexity: O(n log n)

Java Code 

       public int[] mergeSort(int[] arr) {

              // Base case. A list of zero or one elements is sorted, by definition.

              if (arr.length <= 1) {

                     return arr;

              }

              // Recursive case. First, divide the list into equal-sized sublists.

              int middleIndex = (arr.length - 1) / 2;

              int[] left = new int[middleIndex];

              int[] right = new int[arr.length - middleIndex];

              for (int i = 0; i < middleIndex; i++)

                     left[i] = arr[i];

              for (int i = middleIndex, j = 0; i < arr.length; i++, j++)

                     right[j] = arr[i];

              // Recursively sort both sublists

              left = mergeSort(left);

              right = mergeSort(right);

              // Then merge the now-sorted sublists.

              return merge(left, right);

       }

       public int[] merge(int[] left, int[] right) {

              int[] mergedArray = new int[left.length + right.length];

              int leftPointer = 0;

              int rightPointer = 0;

              int mergePointer = 0;

              while (leftPointer < left.length && rightPointer < right.length) {

                     if (left[leftPointer] < right[rightPointer]) {

                           mergedArray[mergePointer++] = left[leftPointer++];

                     } else {

                           mergedArray[mergePointer++] = right[rightPointer++];

                     }

              }

              while (leftPointer < left.length) {

                     mergedArray[mergePointer++] = left[leftPointer++];

              }

              while (rightPointer < right.length) {

                     mergedArray[mergePointer++] = right[rightPointer++];

              }

              return mergedArray;

       }