Scribd
Upload
629 views9 pages

Merge Sort Algorithm and Analysis

Merge sort is a sorting technique that divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. It has a worst-case time complexity of O(n log n), making it one of the most efficient sorting algorithms. The algorithm involves dividing the array, conquering by sorting the sub-arrays, and merging the sorted sub-arrays back together. Its advantages are that it has consistent performance regardless of the initial order of the input and it is faster for large arrays than other algorithms. Its disadvantages are that it is slower for small inputs and uses more memory than other algorithms.

Uploaded by

Mohamed Akel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
629 views9 pages

Merge Sort Algorithm and Analysis

Merge sort is a sorting technique that divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. It has a worst-case time complexity of O(n log n), making it one of the most efficient sorting algorithms. The algorithm involves dividing the array, conquering by sorting the sub-arrays, and merging the sorted sub-arrays back together. Its advantages are that it has consistent performance regardless of the initial order of the input and it is faster for large arrays than other algorithms. Its disadvantages are that it is slower for small inputs and uses more memory than other algorithms.

Uploaded by

Mohamed Akel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
  • Merge Sort
  • Merge Sort Algorithm
  • Algorithm Analysis
  • Program
  • Summary

MERGE SORT

Omar Miftah Askeeb


Outlines

 Merge Sort
 Merge Sort Algorithm
 Algorithm Analysis
 Algorithm Implementation as C Program
 Summary
Merge Sort

 Merge sort is a sorting technique based on divide and conquer


technique. 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.
Merge Sort Algorithm

 Divide: Partition ‘n’ elements array into two sub lists with n/2 elements each
 Conquer: Sort sub list1 and sub list2
 Combine: Merge sub list1 and sub list2
Mergesort Example

8 2 9 4 5 3 1 6
Divide
8 2 9 4 5 3 1 6
Divide
8 2 9 4 5 3 1 6
Divide
1 element 8 2 9 4 5 3 1 6
Merge
2 8 4 9 3 5 1 6
Merge
2 4 8 9 1 3 5 6
Merge
1 2 3 4 5 6 8 9
Algorithm Analysis

 In sorting n objects, merge sort has an average and worst-case performance of


O(nlog n). If the running time of merge sort for a list of length n is T(n), then the
recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm.
Program

#include<stdio.h> int merge(int arr[],int l,int m,int h){

int arr[20]; int arr1[10],arr2[10];

int n1,n2,i,j,k;

int merge_sort(int arr[],int low,int high){ n1=m-l+1;

int mid; n2=h-m;

if(low<high) for(i=0;i<n1;i++)

{ arr1[i]=arr[l+i];

mid=(low+high)/2; for(j=0;j<n2;j++)

merge_sort(arr,low,mid); arr2[j]=arr[m+j+1];

merge_sort(arr,mid+1,high);

merge(arr,low,mid,high);}

return 0;}
Cont.

arr1[i]=9999; int main(){

arr2[j]=9999; int n,i;

i=0;j=0;
for(k=l;k<=h;k++){ printf("Enter the size of array\n");

if(arr1[i]<=arr2[j]) scanf("%d",&n);

arr[k]=arr1[i++]; printf("Enter the elements:");

else for(i=0;i<n;i++)
scanf("%d",&arr[i]);
arr[k]=arr2[j++];}
merge_sort(arr,0,n-1);
return 0;}
printf("Sorted array:");
for(i=0;i<n;i++)
printf("%d",arr[i]);
return 0;}
Summary

Advantages
 It is quicker for larger lists because unlike insertion and bubble sort it doesn't go through the whole
list several times.
 It has a consistent running time, carries out different bits with similar  times in a stage.

Disadvantages
 Slower comparative to the other sort algorithms for smaller tasks.
 goes through the whole process even if the list is sorted .
 uses more memory space to store the sub elements of the initial split list.

MERGE SORT Omar Miftah Askeeb
Outlines Merge Sort Merge Sort Algorithm Algorithm Analysis Algorithm Implementation as C Program Summary
Merge Sort Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being (
Merge Sort Algorithm Divide: Partition ‘n’ elements array into two sub lists with n/2 elements each Conquer: Sort sub list1
Mergesort Example 8 2 9 4 5 3 1 6 8 2 1 6 9 4 5 3 8 2 9 4 5 3 1 6 2 8
Algorithm Analysis In sorting n objects, merge sort has an average and worst-case performance of O(nlog n). If the running
Program #include<stdio.h> int arr[20]; int merge_sort(int arr[],int low,int high){ int mid; if(low<high) { mid=(low
Cont. arr1[i]=9999; arr2[j]=9999; i=0;j=0; for(k=l;k<=h;k++){ if(arr1[i]<=arr2[j]) arr[k]=arr1[i++]; e
Summary Advantages It is quicker for larger lists because unlike insertion and bubble sort it doesn't go through the whole

You might also like