merge sort help in language C with algorithms

merge sort ppt in c

1. Merge Sort

2. Divide And Conquer
•Mergingtwolistsofoneelementeachisthesameas
sortingthem.
•Mergesortdividesupanunsortedlistuntilthe
aboveconditionismetandthensortsthedivided
partsbacktogetherinpairs.
•Specificallythiscanbedonebyrecursivelydividing
theunsortedlistinhalf,mergesortingtheleftside
thentherightsideandthenmergingtheleftand
rightbacktogether.

3. Mergesort Example
8 2 9 4 5 3 1 6
8 2 1 69 4 5 3
82 9 4 53 1 6
2 8 4 9 3 5 1 6
2 4 8 9 1 3 5 6
1 2 3 4 5 6 8 9
Merge
Merge
Merge
Divide
Divide
Divide
1 element
82945316

4. Merge Sort –Example
1826326 43159 1
1826326 43159 1
1826326 43159 1
2618 6 32 1543 1 9
1826326 43159 1
1826326 43159 1
1826 326 15431 9
6 1826321 9 1543
1 6 9 1518263243
1826
1826
1826
32
32
6
6
326
1826326
43
43
15
15
4315
9
9
1
1
9 1
43159 1
1826326 43159 1
1826 6 32
6 26 3218
1543 1 9
1 9 1543
1 6 9 15182632 43
Original Sequence Sorted Sequence

5. Divide-and-conquer Technique
subproblem 2
of size n/2
subproblem 1
of size n/2
a solution to
subproblem 1
a solution to
the original problem
a solution to
subproblem 2
a problem of size n

6. Using Divide and Conquer:
Mergesort strategy
Sorted
Merge
Sorted Sorted
Sort recursively
by Mergesort
Sort recursively
by Mergesort
first last
(first last)2

7. Merge Sort Algorithm
•Divide:Partition‘n’elementsarrayintotwo
sublistswithn/2elementseach
•Conquer:Sortsublist1andsublist2
•Combine:Mergesublist1andsublist2

8. Merge Sort Example
996861558358640

9. Merge Sort Example
996861558358640
9968615 58358640

10. Merge Sort Example
996861558358640
9968615 58358640
8615996 5835 8640

11. Merge Sort Example
996861558358640
9968615 58358640
8615996 5835 8640
996 86155835 86 40

12. Merge Sort Example
996861558358640
9968615 58358640
8615996 5835 8640
996 86155835 86 40
40

13. Merge Sort Example
996 86155835 86 04
40Merge

14. Merge Sort Example
1586699 3558 0486
996 86155835 86 04
Merge

15. Merge Sort Example
6158699 04355886
1586699 3558 0486
Merge

16. Merge Sort Example
046153558868699
6158699 04355886
Merge

17. Merge Sort Example
046153558868699

18. Program
#include<iostream.h>
#include<conio.h>
class MS
{
private:
int A[10];
public:
int n;
int low, high;
void get_data();
void Mergesort(int low, int high);
void Combine(int low, int mid, int high);
void Display();
};
void MS::get_data()
{
cout<<"\n Enter the length of the list";
cin>>n;
cout<<"\n Enter the list elements: \n";
for(int i = 0; i<n; i++)
{
cin>>A[i];
}
}
void MS::Mergesort(int low, int high)
{
int mid;
if(low<high)
{
mid = (low+high)/2; //split the list at mid
Mergesort(low, mid); //first sublist
Mergesort(mid+1, high);//second sublist
Combine(low, mid, high);//merging two sublists
}
}

19. Program
void MS::Combine(int low, int mid, int high)
{
int i,j,k;
int temp[10];
i = low;
j = mid+1;
k = low;
while(i <= mid && j <= high)
{
if(A[i] <= A[j])
{
temp[k] = A[i];
i++;
k++;
}
else
{
temp[k] = A[j];
j++;
k++;
}
}
while(i<=mid)
{
temp[k] = A[i];
i++;
k++;
}
while(j<=high)
{
temp[k] = A[j];
j++;
k++;
}
for(k = low; k <= high; k++)
{
A[k] = temp[k];
}
}

20. Program
void MS::Display()
{
cout<<"\n The sorted array is:\n";
for(int i = 0; i<n; i++)
{
cout<<" "<<A[i];
}
}
int main()
{
MS obj;
obj.get_data();
obj.low=0;
obj.high=(obj.n)-1;
obj.Mergesort(obj.low, obj.high);
obj.Display();
getch();
return 0;
}

21. Time Complexity Analysis
•Worst case:O(nlog
2n)
•Average case:O(nlog
2n​​)
•Best case: O(nlog
2n​​)