Home Data Structures and Algorithms with Java Mergesort in Java

Lesson 26 of 48

In Progress

← Previous Next→

Mergesort in Java

Yasin Cakal

Mergesort is a classic sorting algorithm that is used to sort a given list of elements. It is a divide and conquer algorithm which works by breaking the list of elements into sublists and sorting each sublist until the entire list is sorted. In this article, we will take a look at how Mergesort works, its time complexity, and its space complexity. We will also look at an example of Mergesort in Java to better understand the algorithm. Finally, we will provide five coding exercises with solutions to test the reader’s understanding of Mergesort.

What is Mergesort?

Mergesort is an efficient sorting algorithm that works by breaking down a given list of elements into sublists and sorting each sublist until the entire list is sorted. It is a divide and conquer algorithm which uses recursion to break the list down into smaller sublists and then merges the sorted sublists back together. Mergesort is a stable sorting algorithm, meaning that the order of equal elements will remain the same after the list is sorted.

Mergesort Algorithm

The Mergesort algorithm can be broken down into three steps:

Divide: This is the first step of the Mergesort algorithm. The list of elements is divided into two sublists until each sublist contains only one element. This is done by repeatedly dividing the list in half until each sublist has only one element.
Conquer: This is the second step of the Mergesort algorithm. In this step, the sublists are sorted by comparing the elements in each sublist and merging them in order. This is done by repeatedly comparing the first element of each sublist until the entire list is sorted.
Combine: This is the final step of the Mergesort algorithm. In this step, the sorted sublists are merged together to form the sorted list. This is done by repeatedly merging the sublists until the entire list is sorted.

To illustrate the process of Mergesort, let’s consider the following list: [3,2,1,4,5]. This list can be sorted using Mergesort in the following steps:

Divide the list in half: [3,2,1] [4,5]
Sort each half: [2,3,1] [4,5]
Merge the two halves together: [2,3,1,4,5]

Mergesort Example in Java

Now that we have a basic understanding of the Mergesort algorithm, let’s look at an example of Mergesort in Java. The following code is an example of Mergesort in Java.

public class MergeSort {

    public static void main(String[] args) 
    {
        int[] arr = {10, 7, 8, 9, 1, 5};

        // Print the given array 
        System.out.println("Given Array"); 
        printArray(arr); 

        // Sort the array 
        mergesort(arr, 0, arr.length-1); 

        // Print the sorted array 
        System.out.println("\nSorted Array"); 
        printArray(arr); 
    }

    // Function to sort an array using mergesort algorithm 
    public static void mergesort(int[] arr, int left, int right) 
    {
        if (left < right) 
        {
            // Find the middle point 
            int mid = (left+right)/2; 

            // Sort first and second halves 
            mergesort(arr, left, mid); 
            mergesort(arr , mid+1, right); 

            // Merge the sorted halves 
            merge(arr, left, mid, right); 
        } 
    } 

    // Merge the sorted halves 
    public static void merge(int[] arr, int left, int mid, int right) 
    {
        // Find sizes of two subarrays to be merged 
        int n1 = mid - left + 1; 
        int n2 = right - mid; 

        // Create temp arrays 
        int[] L = new int [n1]; 
        int[] R = new int [n2]; 

        // Copy data to temp arrays 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[left + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[mid + 1+ j]; 

        // Merge the temp arrays 

        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 

        // Initial index of merged subarry array 
        int k = left; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 

        // Copy remaining elements of L[] if any 
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 

        // Copy remaining elements of R[] if any 
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 

    // Function to print an array 
    public static void printArray(int[] arr) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
}

Time and Space Complexity

The time complexity of Mergesort is O(nlog(n)), which is the best time complexity out of all the sorting algorithms. This time complexity is due to the fact that the algorithm has to split the list in half, sort the sublists, and then merge them back together.

The worst case time complexity of Mergesort is also O(nlog(n)), which is the same as the best case time complexity. This is because the algorithm has to always split the list in half, sort the sublists, and then merge them back together, regardless of the input.

The time complexity for access, search, insertion and deletion is also O(nlog(n)), as these operations are dependent on the sorting of the list.

The space complexity of Mergesort is O(n), as it requires additional space to store the sublists while sorting.

Conclusion

In this article, we discussed Mergesort, a classic sorting algorithm. We looked at how the algorithm works, its time complexity, and its space complexity. We also looked at an example of Mergesort in Java to better understand the algorithm. Finally, we provided five coding exercises with solutions to test the reader’s understanding of Mergesort.

Exercises

Write a Java program to implement the Mergesort algorithm.

public class MergeSort {
 
    public static void main(String[] args) 
    {
        int[] arr = {10, 7, 8, 9, 1, 5};
 
        // Print the given array 
        System.out.println("Given Array"); 
        printArray(arr); 
 
        // Sort the array 
        mergesort(arr, 0, arr.length-1); 
 
        // Print the sorted array 
        System.out.println("\nSorted Array"); 
        printArray(arr); 
    }
 
    // Function to sort an array using mergesort algorithm 
    public static void mergesort(int[] arr, int left, int right) 
    {
        if (left < right) 
        {
            // Find the middle point 
            int mid = (left+right)/2; 
 
            // Sort first and second halves 
            mergesort(arr, left, mid); 
            mergesort(arr , mid+1, right); 
 
            // Merge the sorted halves 
            merge(arr, left, mid, right); 
        } 
    } 
 
    // Merge the sorted halves 
    public static void merge(int[] arr, int left, int mid, int right) 
    {
        // Find sizes of two subarrays to be merged 
        int n1 = mid - left + 1; 
        int n2 = right - mid; 
 
        // Create temp arrays 
        int[] L = new int [n1]; 
        int[] R = new int [n2]; 
 
        // Copy data to temp arrays 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[left + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[mid + 1+ j]; 
 
        // Merge the temp arrays 
 
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
 
        // Initial index of merged subarry array 
        int k = left; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
 
        // Copy remaining elements of L[] if any 
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
 
        // Copy remaining elements of R[] if any 
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
 
    // Function to print an array 
    public static void printArray(int[] arr) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
}

Write a Java program to generate a random array of integers and sort it using the Mergesort algorithm.

import java.util.Random; 
 
public class MergeSort {
 
    public static void main(String[] args) 
    {
        // Generate a random array of integers 
        Random rand = new Random(); 
        int[] arr = new int[10]; 
        for (int i=0; i<10; i++) { 
            arr[i] = rand.nextInt(100); 
        } 
 
        // Print the given array 
        System.out.println("Given Array"); 
        printArray(arr); 
 
        // Sort the array 
        mergesort(arr, 0, arr.length-1); 
 
        // Print the sorted array 
        System.out.println("\nSorted Array"); 
        printArray(arr); 
    }
 
    // Function to sort an array using mergesort algorithm 
    public static void mergesort(int[] arr, int left, int right) 
    {
        if (left < right) 
        {
            // Find the middle point 
            int mid = (left+right)/2; 
 
            // Sort first and second halves 
            mergesort(arr, left, mid); 
            mergesort(arr , mid+1, right); 
 
            // Merge the sorted halves 
            merge(arr, left, mid, right); 
        } 
    } 
 
    // Merge the sorted halves 
    public static void merge(int[] arr, int left, int mid, int right) 
    {
        // Find sizes of two subarrays to be merged 
        int n1 = mid - left + 1; 
        int n2 = right - mid; 
 
        // Create temp arrays 
        int[] L = new int [n1]; 
        int[] R = new int [n2]; 
 
        // Copy data to temp arrays 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[left + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[mid + 1+ j]; 
 
        // Merge the temp arrays 
 
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
 
        // Initial index of merged subarry array 
        int k = left; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
 
        // Copy remaining elements of L[] if any 
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
 
        // Copy remaining elements of R[] if any 
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
 
    // Function to print an array 
    public static void printArray(int[] arr) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
}

Write a Java program to find the minimum element in an array of strings using the Mergesort algorithm.

public static String findMin(String[] array) {
	if (array.length == 0) {
		return null;
	}
	if (array.length == 1) {
		return array[0];
	}
	mergeSort(array);
	return array[0];
}

public static void mergeSort(String[] array) {
	if (array.length <= 1) {
		return;
	}
	String[] left = Arrays.copyOfRange(array, 0, array.length / 2); 
    String[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

public static void merge(String[] array, String[] left, String[] right) {
    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex].compareTo(right[rightIndex]) < 0) {
            array[arrayIndex] = left[leftIndex];
            leftIndex++;
        } else {
            array[arrayIndex] = right[rightIndex];
            rightIndex++;
        }
        arrayIndex++;
    }

    while (leftIndex < left.length) {
        array[arrayIndex] = left[leftIndex];
        leftIndex++;
        arrayIndex++;
    }
    while (rightIndex < right.length) {
        array[arrayIndex] = right[rightIndex];
        rightIndex++;
        arrayIndex++;
    }
}

public static void main(String[] args) { 
    String[] array = {"Zebra", "Apple", "Banana", "Cat"};
    String min = findMin(array);
    System.out.println("Min: " + min);
}

Write a Java program to sort an array of objects using the Mergesort algorithm.

public static <T extends Comparable<T>> void mergeSort(T[] array) {
	if (array.length <= 1) {
		return;
	}
	T[] left = Arrays.copyOfRange(array, 0, array.length / 2); 
    T[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

public static <T extends Comparable<T>> void merge(T[] array, T[] left, T[] right) {
    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex].compareTo(right[rightIndex]) < 0) {
            array[arrayIndex] = left[leftIndex];
            leftIndex++;
        } else {
            array[arrayIndex] = right[rightIndex];
            rightIndex++;
        }
        arrayIndex++;
    }

    while (leftIndex < left.length) {
        array[arrayIndex] = left[leftIndex];
        leftIndex++;
        arrayIndex++;
    }
    while (rightIndex < right.length) {
        array[arrayIndex] = right[rightIndex];
        rightIndex++;
        arrayIndex++;
    }
}

public static void main(String[] args) { 
    Dog[] array = {new Dog("Fido", 5), new Dog("Barky", 3), new Dog("Spot", 10)};
    mergeSort(array);
    for (Dog dog : array) {
        System.out.println(dog.name + " " + dog.age);
    }
}

Write a Java program to sort an array of strings using the Mergesort algorithm.

public static void mergeSort(String[] array) {
	if (array.length <= 1) {
		return;
	}
	String[] left = Arrays.copyOfRange(array, 0, array.length / 2); 
    String[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

public static void merge(String[] array, String[] left, String[] right) {
    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex].compareTo(right[rightIndex]) < 0) {
            array[arrayIndex] = left[leftIndex];
            leftIndex++;
        } else {
            array[arrayIndex] = right[rightIndex];
            rightIndex++;
        }
        arrayIndex++;
    }

    while (leftIndex < left.length) {
        array[arrayIndex] = left[leftIndex];
        leftIndex++;
        arrayIndex++;
    }
    while (rightIndex < right.length) {
        array[arrayIndex] = right[rightIndex];
        rightIndex++;
        arrayIndex++;
    }
}

public static void main(String[] args) { 
    String[] array = {"Zebra", "Apple", "Banana", "Cat"};
    mergeSort(array);
    System.out.println(Arrays.toString(array));
}

Data Structures and Algorithms with Java

Participants 676