Merge Sort Implementation in Java

Merge Sort

Mergesort is a divide and conquer algorithm and works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

During the Merge Sort process the object in the collection are divided into two collections. To split a collection, Merge Sort will take the middle of the collection and split the collection into its left and its right part.

The resulting collections are again recursively sorted via the Merge Sort algorithm.

Once the sorting process of the two collections is finished, the result of the two collections is combined. To combine both collections Merge Sort start at each collection at the beginning. It pick the object which is smaller and inserts this object into the new collection. For this collection it now selects the next elements and selects the smaller element from both collection.

Once all elements from both collections have been inserted in the new collection, Merge Sort has successfully sorted the collection.

To avoid the creation of too many collections, typically one new collection is created and the left and right side are treated as different collections.

Merge Sort Example - GIF Format

Merge Sort in Java

 public class MergeSort {  
      private int[] numbers;  
      private int[] helper;  
      public void sort(int[] values) {  
           this.numbers = values;  
           this.helper = new int[values.length];  
           mergesort(0, values.length - 1);  
      }  
      private void mergesort(int low, int high) {  
           // check if low is smaller then high, if not then the array is sorted
           if (low < high) {  
                // Get the index of the element which is in the middle
                int middle = low + (high - low) / 2;  
                // Sort the left side of the array
                mergesort(low, middle);  
                // Sort the right side of the array
                mergesort(middle + 1, high);  
                // Combine them both
                merge(low, middle, high);  
           }  
      }  
      private void merge(int low, int middle, int high) {  
           // Copy both parts into the helper array
           for (int i = low; i <= high; i++) {  
                helper[i] = numbers[i];  
           }  
           int i = low;  
           int j = middle + 1;  
           int k = low;  
           // Copy the smallest values from either the left or the right side back
           // to the original array
           while (i <= middle && j <= high) {  
                if (helper[i] <= helper[j]) {  
                     numbers[k] = helper[i];  
                     i++;  
                } else {  
                     numbers[k] = helper[j];  
                     j++;  
                }  
                k++;  
           }  
           // Copy the rest of the left side of the array into the target array
           while (i <= middle) {  
                numbers[k] = helper[i];  
                k++;  
                i++;  
           }  
      }  
      public static void main(String[] args) {  
           int[] numbers = { 84, 90, 69, 76, 86, 94, 75, 91 };  
           print("Before: ", numbers);  
           MergeSort mergeSort = new MergeSort();  
           mergeSort.sort(numbers);  
           print("Before: ", numbers);  
      }  
      public static void print(String label, int[] numbers) {  
           System.out.print(label + ": ");  
           for (int i : numbers) {  
                System.out.print(i + " ");  
           }  
           System.out.println();  
      }  
 }  

Complexity Analysis

Merge Sort Complexity

Case	Complexity
Worst case performance	O(n log n)
Best case performance	O(n log n)
Average case performance	O(n log n)

Merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list. Slow random-access performance of a linked list makes some other algorithms (such as Quick Sort) perform poorly, and others (such as Heap Sort) completely impossible.

References

Merg Sort from Wikipedia
Merge Sort in Java - Tutorial by Lars Vogel