Sorting is a fundamental operation in computer science, and there are many algorithms available to perform this task. One of the most popular and efficient sorting algorithms is Merge Sort. In this tutorial, we will learn how to implement Merge Sort in Java.

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm that works by recursively dividing the input Array into two halves, sorting each half, and then merging the sorted halves back together. The algorithm has a time complexity of O(n log n), which makes it one of the fastest sorting algorithms available.

Implementing Merge Sort in Java

To implement Merge Sort in Java, we need to create a function that takes an array of integers as input and returns a sorted array. Here’s the basic outline of the function:

public static int[] mergeSort(int[] arr) {
    // Base case: if the array is empty or has only one element, it is already sorted
    if (arr.length 

Let’s go through each step of the function in more detail. Step 1: Base case The first step of the function is to check if the input array is empty or has only one element. If it is, then the array is already sorted, and we can simply return it. This is the base case of the recursive function.

if (arr.length 

Step 2: Divide the array into two halves If the input array has more than one element, we need to divide it into two halves. To do this, we create two new arrays: one for the left half and one for the right half. We use the System.arraycopy() method to copy the elements from the input array into the new arrays.

int[] left = new int[arr.length / 2];
int[] right = new int[arr.length - left.length];
System.arraycopy(arr, 0, left, 0, left.length);
System.arraycopy(arr, left.length, right, 0, right.length);

Step 3: Recursively sort each half Once we have divided the input array into two halves, we recursively call the mergeSort() function on each half. This will sort each half of the array.

left = mergeSort(left);
right = mergeSort(right);

Step 4: Merge the sorted halves Finally, we merge the sorted left and right halves back together. To do this, we create a new array that is the same size as the input array. We then iterate over both halves of the input array, comparing the first element of each half and adding the smaller element to the new array. We continue this process until we have added all the elements from both halves to the new array.

public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    
    while (i 

Step 5: Putting it all together Now that we have implemented the merge() function, we can put everything together in the mergeSort() function.

public static int[] mergeSort(int[] arr) {
    // Base case: if the array is empty or has only one element, it is already sorted
    if (arr.length 

Testing the Merge Sort Function

Now that we have implemented the Merge Sort function, let’s test it out with some sample input.

public static void main(String[] args) {
    int[] arr = {5, 2, 9, 1, 5, 6};
    arr = mergeSort(arr);
    System.out.println(Arrays.toString(arr));
}

When we run this code, we should see the following output:

[1, 2, 5, 5, 6, 9]

This confirms that our Merge Sort function is working correctly.

Conclusion

In this tutorial, we learned how to implement Merge Sort in Java. We saw how Merge Sort works by recursively dividing the input array into two halves, sorting each half, and then merging the sorted halves back together. We also saw how to test our Merge Sort function with sample input. Merge Sort is a very efficient sorting algorithm with a time complexity of O(n log n), and it is widely used in practice.

Related Articles

No related articles found.

The post Implementing Merge Sort in Java: Step-by-Step Tutorial appeared first on Java Master.