Merge Sort Algorithm
Merge Sort:
Merge Sort is a Divide and Conquer algorithm ( or It follows divide and conquer design technique.)
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
Below is the basic algorithm for merge sort:
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
Example:
The following diagram from wikipedia() shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
Execution Flow:
Here is the implementation of Merge Sort in java:
Approach 1:
Program:
class MergeSort {
// 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);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array");
printArray(arr);
}
}
Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Explanation:
As we know the execution of program starts from main method. In main method we are declaring array initialized then calling sort method by passing array, start index, ending index as parameters of sort method.
In sort method we are calculating mid and recursively calling sort method for left half and right half of the array. This will continues until we get single element in the array (single element of array is considered as sorted array(this is considered as small problem in dynamic programming approach))here the if condition becomes false then the execution goes to merge method.
In merge method we are storing the elements of two half arrays into two different arrays (L, R) and using two pointer approach we are inserting the elements in array(based on either we need ascending or descending order here ascending order ) .
Approach 2:
Program:
// example of merge sort in Java
// merge function take two intervals
// one from start to mid
// second from mid+1, to end
// and merge them in sorted order
void merge(int Arr[], int start, int mid, int end) {
// create a temp array
int temp[] = new int[end - start + 1];
// crawlers for both intervals and for temp
int i = start, j = mid+1, k = 0;
// traverse both arrays and in each iteration add smaller of both elements in temp
while(i <= mid && j <= end) {
if(Arr[i] <= Arr[j]) {
temp[k] = Arr[i];
k += 1; i += 1;
}
else {
temp[k] = Arr[j];
k += 1; j += 1;
}
}
// add elements left in the first interval
while(i <= mid) {
temp[k] = Arr[i];
k += 1; i += 1;
}
// add elements left in the second interval
while(j <= end) {
temp[k] = Arr[j];
k += 1; j += 1;
}
// copy temp to original interval
for(i = start; i <= end; i += 1) {
Arr[i] = temp[i - start]
}
}
// Arr is an array of integer type
// start and end are the starting and ending index of current interval of Arr
void mergeSort(int Arr[], int start, int end) {
if(start < end) {
int mid = (start + end) / 2;
mergeSort(Arr, start, mid);
mergeSort(Arr, mid+1, end);
merge(Arr, start, mid, end);
}
}
Explanation:
In this approach instead of taking two additional arrays we are taking one temp array of size of two half arrays and storing the values in the temp by traversing through the arrays (two half arrays) and finally the values of temp array are stored in the array based on starting index.
I think from my explanation you got a basic idea about merge sort 🙂.
Reference👉 Merge Sort Reference || Merge Sort Reference
Happy Coding💻:-)
Comments
Post a Comment