Linked Lists
What is Linked Lists? Singly Linked Lists Doubly Linked Lists Circular Linked Lists Header Linked ListsStacks
What is Stack? Push Operation Pop Operation Peek Operation Linked Stack Multiple StacksQueues
What is Queues? Linear QueueSearching
What is Searching? Linear Search Binary Search Interpolation Search Jump SearchSorting
What is Sorting? Bubble Sort Insertion Sort Selection Sort Merge Sort Quick Sort Radix Sort Heap Sort Shell Sort Tree SortHashing
What is Hashing? What is Collision?The ones who are crazy enough to think they can change the world are the ones who do.- Steve Jobs
Merge Sort
Merge sort algorithm uses the technique of divide, conquer and combine.
Divide
Divide the elements in an array into two sub-array of n/2 elements of each sub-arrays.
Conquer
Sorting the two sub-arrays recursively using merge sort.
Combine
Merging the two sorted sub-arrays of size n/2 to produce the sorted arrays of n elements.
Advantages - Merge Sort
- Merge sort algorithm is best case for sorting slow-access data e.g) tape drive.
- Merge sort algorithm is better at handling sequential - accessed lists.
Disadvantages - Merge Sort
- The running time of merge sort algorithm is 0(n log n). which turns out to be the worse case.
- Merge sort algorithm requires additional memory spance of 0(n) for the temporary array TEMP.
C program - Merge Sort
Here is the program to demonstrate Merge Sort.
merge-sort.c
#include <stdio.h>
void merge(int a[], int, int, int);
void merge_sort(int a[], int, int);
int main()
{
int arry[10],i,n;
printf("\n Enter the size of the array : ");
scanf("%d",&n);
printf("\n Enter %d elements in the array : \n",n);
for(i=0; i<n; i++)
scanf("%d", &arry[i]);
merge_sort(arry, 0, n-1);
printf("\n Sorted Array in ascending order is : \n");
for(i=0; i<n; i++)
printf("%d ",arry[i]);
return 0;
}
void merge(int arry[], int beg, int mid, int end)
{
int i = beg, j = mid + 1, index = beg, temp[10], k;
while((i <= mid) && (j <= end))
{
if(arry[i] < arry[j])
{
temp[index] = arry[i];
i++;
}
else
{
temp[index] = arry[j];
j++;
}
index++;
}
if(i > mid)
{
while(j <= end)
{
temp[index] = arry[j];
j++;
index++;
}
}
else
{
while(i <= mid)
{
temp[index]= arry[i];
i++;
index++;
}
}
for(k = beg;k < index; k++)
arry[k] = temp[k];
}
void merge_sort(int arry[], int beg, int end)
{
int mid;
if(beg < end)
{
mid = (beg + end) / 2;
merge_sort(arry, beg, mid);
merge_sort(arry, mid+1, end);
merge(arry, beg, mid, end);
}
}
Enter the size of the array : 5 Enter 5 elements in the array : 4 3 1 2 5 Sorted Array in ascending order is : 1 2 3 4 5
Related to Merge Sort
Report Us
We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.
Report
Programming
Electrical
Interview
© Copyright 2019