Back to Course

Data Structures and Algorithms with Java

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with Java
  2. Importance of Data Structures and Algorithms in Programming with Java
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with Java
  4. Basic Java Concepts Review
    Variables and Data Types in Java
  5. Control Flow Statements in Java
  6. Classes and Objects in Java
  7. Methods and Constructors in Java
  8. Basic Input and Output in Java
  9. Data Structures
    Arrays in Java
  10. Stacks and Queues in Java
  11. Linked Lists in Java
  12. Hash Tables in Java
  13. Trees in Java
  14. Types of Trees
    Binary Search Trees in Java
  15. Cartesian Trees in Java
  16. B-Trees in Java
  17. Red-Black Trees in Java
  18. Splay Trees in Java
  19. AVL Trees in Java
  20. KD Trees in Java
  21. Min Heap in Java
  22. Max Heap in Java
  23. Trie Trees in Java
  24. Suffix Trees in Java
  25. Sorting Algorithms
    Quicksort in Java
  26. Mergesort in Java
  27. Timsort in Java
  28. Heapsort in Java
  29. Bubble Sort in Java
  30. Insertion Sort in Java
  31. Selection Sort in Java
  32. Tree Sort in Java
  33. Shell Sort in Java
  34. Bucket Sort in Java
  35. Radix Sort in Java
  36. Counting Sort in Java
  37. Cubesort in Java
  38. Searching Algorithms
    Linear Search in Java
  39. Binary Search in Java
  40. Graph Algorithms
    Breadth First Search (BFS) in Java
  41. Depth First Search (DFS) in Java
  42. Dijkstra's Algorithm in Java
  43. Algorithm Design Techniques
    Greedy Algorithms in Java
  44. Dynamic Programming in Java
  45. Divide and Conquer in Java
  46. Backtracking in Java
  47. Randomized Algorithms in Java
  48. Conclusion
    Recap of DSA in Java

Participants 445

Show more

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:

  1. 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.
  2. 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.
  3. 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:

  1. Divide the list in half: [3,2,1] [4,5]
  2. Sort each half: [2,3,1] [4,5]
  3. 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));
}