Merge Sort in Java

What is Merge Sort?

The Merge Sort is the most common algorythm for sorting data using the “divide and conquer” technique. In this algorithm, the problem is divided into subproblems and then after sorting they are merged together. Let us say we have a list of unsorted numbers, the result of a class for a certain subject. To sort them by ascending order we will need to place them in a list starting from low to high. In this Merge Sort algorithm, the list will be divided into smaller lists to sort them into an ascending order and then it will merge the results for better understanding. Merge Sort in Java can be explained through an example of an array {6,9,8,2,4,1}, consider it as a result of a class test out of 10. The array (of results) will be repeatedly divided into smaller chunks until their size is 1. Then the process of merging takes place while sorting the numbers simultaneously. This will provide us with a result that begins with the lowest marks to the highest marks received. This array will be divided into two arrays which will contain 3 elements each as shown below in step 2 and it keeps on dividing until unity is reached in step 4. Then the Merge Sort algorithm starts to sort the numbers one step at a time (step 5) and then merges the numbers into a bigger array in steps 6 & 7.

Implementation

In the implementation we will write code for the merge sort algorithm in Java. The variables required will be the input array and the length of the array. These two parameters will further be used to introduce further parameters to create the merge sort function. Let's have a look at the snippet below to understand the general working of the Merge Sort Algorithm in Java.

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

First through the if condition Beginning and End are used to determine the Middle. Then in the next step, 2 new subarrays are created starting from the Beginning to the Middle and the other starting from the Middle +1 to the End. These arrays are divided until their length becomes 1 and then through the Merge Function the sorted subarrays Beginning, Middle, Middle+1 and End all are merged back to acquire the solution.

Example

The following code in Java explains the merge sort algorithm:

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

Output

Conclusion

Merge Sort in Java is a simple algorithm to acquire a sorted list from an unsorted list of numbers. The basic method of ‘divide and conquer’ is applied to access the sorted array from an unsorted array.