In this article, we will discuss working and implementation of Merge Sort algorithm.
Merge sort is an example of the divide and conquer strategy. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.
Merge sort first divides the array into equal halves and then combines them in a sorted manner.
It works on the below principle:
- Divide list into sub list of about half size in each iteration until each sublist has only one element.
- Merge each sublist repeatedly to create a sorted list. It will run until we have only 1 sorted list. This will be the sorted list.
How Merge Sort Works?
To understand merge sort, we take an unsorted array as the following −
We know that merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved. We see here that an array of 8 items is divided into two arrays of size 4.
This does not change the sequence of appearance of items in the original. Now we divide these two arrays into halves.
We further divide these arrays and we achieve an atomic value which can no more be divided.
Now, we combine them in exactly the same manner as they were broken down. Please note the color codes given to these lists.
We first compare the element for each list and then combine them into another list in a sorted manner. We see that 20 and 23 are in sorted positions. We compare 25 and 21 and in the target list of 2 values, we put 21 first, followed by 25. Similarly, compare 30 and 10 these are not sorted so let's sort it and compare 65 and 15 these are also not sorted so sort it out. The final outcome is:
In the next iteration of the combining phase, we compare lists of two data values and merge them into a list of found data values placing all in a sorted order. Note that the items should be sorted while combining these halves.
After the final merging, the list should look like this −
10 15 20 21 23 25 30 65
Now we should learn some programming aspects of merge sorting.
Let's write a simple logic for Merge sort algorithm in Java.
Simple Implementation of Merge Sort
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* 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[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 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 = l;
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++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
The above code sorts only integer array but what about if we want to sort Strings, Dates, Doubles etc. I have implemented a generic merge sort algorithm to sort any data type the implements Comparable interface.
Generic Implementation of Merge Sort
Let's create a generic implementation of Merge Sort algorithm so that we can sorting Integer, String, Double etc. This program sorts according to the natural ordering of its elements. Wrapper classes and String internally implement the Comparable interface.
This program demonstrates sorting Integer and String array using Merge Sort Algorithm.
import java.util.Arrays;
/**
* Generic implementation of Generic Merge Sort
* @author Ramesh Fadatare
*
*/
public class GenericMergeSort {
/**
* This method implements the Generic Merge Sort
*
* @param unsorted
* the array which should be sorted
* @param <T>
* Comparable class
* @return sorted array
*/
@SuppressWarnings("unchecked")
public <T extends Comparable<T>> T[] mergeSort(T[] unsorted) {
T[] tmp = (T[]) new Comparable[unsorted.length];
doSort(unsorted, tmp, 0, unsorted.length - 1);
return unsorted;
}
/**
*
* @param arr
* The array to be sorted
* @param temp
* The copy of the actual array
* @param left
* The first index of the array
* @param right
* The last index of the array Recursively sorts the array in
* increasing order
**/
private static <T extends Comparable<T>> void doSort(T[] arr, T[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
doSort(arr, temp, left, mid);
doSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
/**
* This method implements the merge step of the merge sort
*
* @param arr
* The array to be sorted
* @param temp
* The copy of the actual array
* @param left
* The first index of the array
* @param mid
* The middle index of the array
* @param right
* The last index of the array merges two parts of an array in
* increasing order
**/
private static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
System.arraycopy(arr, left, temp, left, right - left + 1);
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i].compareTo(temp[j]) <= 0) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
while (j <= right) {
arr[k] = temp[j];
j++;
k++;
}
}
// Driver program
public static void main(String[] args) {
// Integer Input
Integer[] array = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
GenericMergeSort mergeSort = new GenericMergeSort();
System.out.println("Before sorting the array elements : " + Arrays.toString(array));
mergeSort.mergeSort(array);
System.out.println("After sorting the array elements : " + Arrays.toString(array));
// String Input
String[] stringArray = { "c", "a", "e", "b", "d" };
System.out.println("Before sorting the array elements : " + Arrays.toString(stringArray));
mergeSort.mergeSort(stringArray);
System.out.println("After sorting the array elements : " + Arrays.toString(stringArray));
}
}
Output:
Before sorting the array elements : [4, 23, 6, 78, 1, 54, 231, 9, 12]
After sorting the array elements : [1, 4, 6, 9, 12, 23, 54, 78, 231]
Before sorting the array elements : [c, a, e, b, d]
After sorting the array elements : [a, b, c, d, e]Performance
- Worst case complexity: Θ(nlogn)
- Best case complexity: Θ(nlogn)
- Average case complexity: Θ(nlogn)
- Worst case space complexity: Θ(n) auxiliary
Comments
Post a Comment
Leave Comment