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));
}