Merge Sort

11/December/2014 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

Merge Sort:

The merge sort is fairly straight forward, but coding it can be quite tricky, but hopefully both the code and explanation below will help you to know how it works.

    
        /**
         * Uses the merge sort method to sort an array in ascending order.
         *
         * @param arr 
         *        The array.
         *
         * @return 
         *        The sorted array.
         */
        public int[] sort(final int[] arr) {
            // If the array has zero, or one, element, then it is already sorted.
            if (arr.length == 0 || arr.length == 1) {
                return arr;
            }

            // Split the array into two halves.
            int half = arr.length/2;
            int[] arrA = new int[half];
            int[] arrB = new int[arr.length - half];

            // Fill both halves with the values from arr.
            for (int i = 0 ; i < half ; i++) {
                arrA[i] = arr[i];
            }

            for (int i = half ; i < arr.length ; i++) {
                arrB[i - half] = arr[i];
            }

            // Recursively call the sort() method on both halves.
            arrA = sort(arrA);
            arrB = sort(arrB);

            // Combine the two sorted arrays while sorting.
            int[] arrC = new int[arr.length];

            int arrAIndex = 0, arrBIndex = 0, arrCIndex = 0;

            while (arrAIndex < arrA.length && arrBIndex < arrB.length) {
                if(arrA[arrAIndex] < arrB[arrBIndex]) {
                    arrC[arrCIndex] = arrA[arrAIndex];
                    arrAIndex++;
                } else {
                    arrC[arrCIndex] = arrB[arrBIndex];
                    arrBIndex++;
                }
                arrCIndex++;
            }

            // Because the above loop doesn't work for all elements we must
            // copy whatever elements remain into arrC.
            while (arrAIndex < arrA.length) {
                arrC[arrCIndex] = arrA[arrAIndex];
                arrCIndex++;
                arrAIndex++;
            }

            while (arrBIndex < arrB.length) {
                arrC[arrCIndex] = arrB[arrBIndex];
                arrCIndex++;
                arrBIndex++;
            }

            return arrC;
        }
    

The merge sort works by continuously splitting the original array into halves until each element is in its own array. Once this is done, the algorithm starts with the first two elements, puts them in sorted order, and returns them. Then it takes the returned array of two elements, adds in the next element, sorts them, returns the new array of three sorted elements, and continues on until the final sorted array is returned.

In the above image, we begin with an unsorted array of colors. We will be sorting by the names of each color. The algorithm begins with the top array and ends with the bottom array. The red lines show an array being halved and the purple lines show two arrays being combined and sorted.

Additional Information: