Merge sort algorithm
Merge Sort Algorithm
Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time.
Merge sort runs in O(n*log n) time in all the cases.
Divide and Conquer
If we can break a single big problem into smaller sub-problems, solve the smaller sub-problems and combine their solutions to find the solution for the original big problem, it becomes easier to solve the whole problem.
In Merge Sort, the given unsorted array with n elements, is divided into n subarrays, each having one element, because a single element is always sorted in itself. Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced.
The concept of Divide and Conquer involves three steps:
Divide the problem into multiple small problems.
Conquer the subproblems by solving them. The idea is to break down the problem into atomic subproblems, where they are actually solved.
Combine the solutions of the subproblems to find the solution of the actual problem.
How Merge Sort Works?
As we have already discussed that merge sort utilizes divide-and-conquer rule to break the problem into sub-problems, the problem in this case being, sorting a given array.
In merge sort, we break the given array midway, for example if the original array had 6 elements, then merge sort will break it down into two subarrays with 3 elements each.
But breaking the orignal array into 2 smaller subarrays is not helping us in sorting the array.
So we will break these subarrays into even smaller subarrays, until we have multiple subarrays with single element in them. Now, the idea here is that an array with a single element is already sorted, so once we break the original array into subarrays which has only a single element, we have successfully broken down our problem into base problems.
And then we have to merge all these sorted subarrays, step by step to form one single sorted array.
Let's consider an array with values {14, 7, 3, 12, 9, 11, 6, 12}
Below, we have a pictorial representation of how merge sort will sort the given array.
In merge sort we follow the following steps:
Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps.
If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements.
Conquer means sort the two sub-arrays recursively using the merge sort.
Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array.
The main idea behind merge sort is that, the short list takes less time to be sorted.
Complexity
Algorithm
Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
Step 2: Repeat while (I <= MID) AND (J<=END)
IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]
Step 3: [Copy the remaining
elements of right sub-array, if
any]
IF I > MID
Repeat while J <= END
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of
left sub-array, if any]
ELSE
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]Step 4: [Copy the contents of TEMP back to ARR] SET K = 0
Step 5: Repeat while K < INDEX
SET ARR[K] = TEMP[K]
SET K = K + 1
[END OF LOOP]Step 6: Exit
MERGE_SORT(ARR, BEG, END)
Step 1: IF BEG < END
SET MID = (BEG + END)/2
CALL MERGE_SORT (ARR, BEG, MID)
CALL MERGE_SORT (ARR, MID + 1, END)
MERGE (ARR, BEG, MID, END)
[END OF IF]Step 2: END
C- Program
#include<stdio.h>
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void main ()
{
int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i;
mergeSort(a,0,9);
printf("printing the sorted elements");
for(i=0;i<10;i++)
{
printf("\n%d\n",a[i]);
}
}
void mergeSort(int a[], int beg, int end)
{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
mergeSort(a,beg,mid);
mergeSort(a,mid+1,end);
merge(a,beg,mid,end);
}
}
void merge(int a[], int beg, int mid, int end)
{
int i=beg,j=mid+1,k,index = beg;
int temp[10];
while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
temp[index] = a[i];
i = i+1;
}
else
{
temp[index] = a[j];
j = j+1;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index] = a[j];
index++;
j++;
}
}
else
{
while(i<=mid)
{
temp[index] = a[i];
index++;
i++;
}
}
k = beg;
while(k<index)
{
a[k]=temp[k];
k++;
}
}
Output:
printing the sorted elements
7
9
10
12
23
23
34
44
78
101
Comments
Post a Comment