MERGE SORTING: – Merging means combining two sorted lists into one sorted list. For this, the elements from both the sorted lists are compared. The smaller of both the elements are then stored in the third array Merge Sort is a sorting algorithm that uses the idea of divide and conquers This algorithm divides the array into smaller files, sorts them separately, and then merges them.
The major work is done in the merge procedure, which is a PIN) operation. The only disadvantage of merge sort is that it uses an extra temporary array of the same size. as that of the input array to merge the two arrays. The elements of the temporary array are copied back to the original array before the next merging. In merge sort the splitting is simple but the joining is hard (merging the two sorted files). In quick sort, the splitting is hard (partitioning), and the joining is simple (the two halves and the pivot automatically form a sorted array).
Algorithm for Merge sorting in c programming.
MERGE_SORT (A, N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1. Set SIZE:= 1.
2. Repeat Steps 3 to 7 While SIZE < N:
3. Set L1 = 1, K = 1.
4. Repeat Steps While (L1 + SIZE) < = N:
(a) Set L2: L1 + SIZE.
(b) Set U1: L2-1.
(c) If U1 + SIZE < = N, then:
Set U2 := U1 + SIZE.
(d) Else:
Set U2 = N.
[End of if structure.]
(e) Repeat Steps For I:= L1 to U1 and J := L2 to U2:
if A [I] < A [J], then:
(i) Set TEMP [K] := A [I].
(ii) Set I: = I + 1
Else:
(i) Set TEMP [K] := A [J]
(ii) Set J := J + 1
[End of if structure]
Set K := K + 1
[End of Step (e) loop]
(f) Repeat Steps While I < = U1.
(i) Set TEMP [K] := A [I]
(ii) Set K := K + 1
(iii) Set I := I + 1
[End of Step (f) loop.]
(g) Repeat Steps While J < = U2:
(i) Set TEMP [K] := A [J]
(ii) Set K := K + 1
(iii) Set J := J +1.
[End of Step (g) loop]
(h) Set L1 := U2 + 1
[End of Step 4 loop.]
5. Repeat Steps While L1 <= N:
(i) Set TEMP [L1]: = A [L1]
(ii) Set L1: L1 + 1.
[End of Step 5 loop]
6. Repeat Steps For I: = 1 to N:
(i) Set A [I] = TEMP [I]
(ii) Set I: = I + 1
[End of Step 6 loop.]
7. Set SIZE:= SIZE*2.
[End of Step 2 loop.]
8. Return.
Merge sorting (Non-Recursive) program in c Programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void merge_sort(int [], int);
void main()
{
int a[SIZE], n, i;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/*Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d ", i+1);
scanf("%d",&a[i]);
}
merge_sort(a,n);
/* Output Array */
for(i=0;i<n;i++)
printf("%dn",a[i]);
getch();
}
void merge_sort(int a[], int n)
{
int i,j,k,lb1,ub1,ub2,t[SIZE],sz;
sz = 1;
while(sz < n)
{
lb1 = 0;
k = 0;
while((lb1 + sz) < n)
{
lb2 = lb1 + sz;
ub1 = lb2 - 1;
ub2 = (ub1 + sz) < n ? (ub + sz) : n-1;
/* merging */
for(i=lb1, j=lb2; i<=ub1 && j <= ub2; k++)
{
if(a[i] < a[j])
t[k] = a[i++];
else
t[k] = a[j++];
}
/* remaining of 1st file */
while(i <= ub1)
t[k++] = a[i++];
/*remaining of 2nd file*/
while(j <= ub2)
t[k++] = a[i++];
lb1 = ub2 + 1;
}
/* copy any remaining file not in pair*/
while(k < n)
{
t[k] = a[k];
k++;
}
/* copy t array into a*/
for(i=0; i<n; n++)
a[i] = t[i];
sz = 2*sz;
}
}Merge sorting (Recursive) program in c programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void merging(int [], int, int, int, int);
void mergesort(int [], int, int);
void main()
{
int a[SIZE],i,n;
print("Enter how many elements");
scanf("%d",&n);
/*input array */
for(i=0;i<n;i++)
{
printf("Enter element %d",i+1);
scanf("%d",&a[i]);
}
mergesort(a,0,n-1);
/* Output array */
for(i=0;i<n;i++)
printf("%d",a[i]);
getch();
}
void merging(int a[], int l1, int u1, int l2, int u2)
{
int i,j,k,t[SIZE];
for(i=l1, j=l2,k=l1;i<=u1 && j <= u2; k++)
{
if(a[i] < a[j])
t[k] = a[i++];
else
t[k] = a[j++];
}
/*Remaining of first file */
while(i <= u1)
t[k++] = a[i++];
/* Remaining of second file */
while(j <= u2)
t[k++] = a[j++];
for(i=l1;i<=u2;i++)
a[i] = t[i];
}
void mergesort(int a[], int lb, int ub)
{
int mid;
if(lb < ub)
{
mid = (lb + ub)/2;
mergesort(a,lb,mid);
mergesort(a,mid+1,ub);
merging(a,lb,mid,mid+1,ub);
}
}Also, Read