Merge sort algorithm power point presentation

University of Science & Technology, Chittagong Faculty of Science, Engineering & Technology Department: Computer Science & Engineering Course Title: Algorithm lab Course code: CSE 222 Semester: 4th Batch: 25th

Submitted by: Name: Md Abdul Kuddus Roll: 15010102 Submitted to: Sohrab Hossain , Assistant Professor, Department of CSE,FSET,USTC

Presentation Topic: MERGE SORT

MERGE SORT : Merge sort was invented by John Von Neumann (1903 - 1957) Merge sort is divide & conquer technique of sorting element Merge sort is one of the most efficient sorting algorithm Time complexity of merge sort is O(n log n)

DIVIDE & CONQUER • DIVIDE : Divide the unsorted list into two sub lists of about half the size • CONQUER : Sort each of the two sub lists recursively. If they are small enough just solve them in a straight forward manner • COMBINE : Merge the two-sorted sub lists back into one sorted list

DIVIDE & CONQUER TECHNIQUE a problem of size n sub problem 1 of size n/2 sub problem 2 of size n/2 a solution to sub problem 1 a solution to sub problem 2 a solution to the original problem

MERGE SORT PROCESS : • The list is divided into two equal (as equal as possible) part • There are different ways to divide the list into two equal part • The following algorithm divides the list until the list has just one item which are sorted • Then with recursive merge function calls these smaller pieces merge

MERGE SORT ALGORITHM : • Merge(A[],p , q , r) { n1 = q – p + 1 n2 = r – q Let L[1 to n1+1] and R[1 to n2+1] be new array for(i = 1 to n1) L[i] = A[p + i - 1] for(j = 1 to n2) R[j] = A[q + j] L[n1 + 1] = infinity R[n2 + 1] = infinity

for(k = p to r) { if ( L[i] <= R[j]) A[k] = L[j] i = i + 1 else A[k] = R[j] j = j + 1 }

Merge sort (A, p, r) { if (p < r) // check for base case q = [ (p + r)/2 ] // divide step Merge sort (A, p, q) // conquer step Merge sort (A, q+1, r) // conquer step Merge sort (A, p, q, r) // conquer step }

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1K 1 2 3 4 5 6 7 8

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4 5K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4 5 6K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4 5 6 7K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4 5 6 7 8K

MERGE SORT EXAMPLE : 1 5 7 8 2 4 6 9 p q q + 1 r 1 5 7 8 infinity 2 4 6 9 infinityL R i=1 2 3 4 5 j=1 2 3 4 5 1 2 4 5 6 7 8 9K

/* Merging (Merge sort) */ #include <stdio.h> void main () { int a[10] = {1, 5, 11, 30, 2, 4, 6, 9}; int i,j,k,n1,n2,p,q,r; p = 1; q = 4; r = 8; n1 = q-p+1; n2 = r-q; int L[n1+1]; int R[n2+1]; for( i=0; i<n1; i++) L[i] = a[p+i-1]; for( i=0; i<n1; i++) printf("%d n", L[i]); for( j=0; j<n2; j++) R[j] = a[q+j];

L[n1] = 300; R[n2] = 300; i=0; j=0; for( k=0; k<r; k++) { if (L[i] <= R[j]) { a[k] = L[i]; i++; } else { a[k] = R[j]; j++;

IMPLEMENTING MERGE SORT : There are two basic ways to implement merge sort In place : Merge sort is done with only the input array Double storage : Merging is done with a temporary array of the same size as the input array

MERGE-SORT ANALYSIS : Time, merging log n levels Total time for merging : O (n log n) Total running time : Order of n log n Total space : Order of n n/2 n/2 n/4 n/4 n/4 n/4 n

Performance of MERGESORT : • Unlike quick sort, merge sort guarantees O (n log n)in the worst case • The reason for this is that quick sort depends on the value of the pivot whereas merge sort divides the list based on the index • Why is it O (n log n ) ? • Each merge will require N comparisons • Each time the list is halved • So the standard divide & conquer recurrence applies to merge sort T(n) = 2T * n/2 + (n)

FEATURES OF MERGE SORT : • It perform in O(n log n ) in the worst case • It is stable • It is quite independent of the way the initial list is organized • Good for linked lists. Can be implemented in such a way that data is accessed sequentially. Drawbacks : It may require an array of up to the size of the original list. This can be avoided but the algorithm becomes significantly more complicated making it worth while. Instead of making it complicated we can use HEAP SORT which is also O(n log n ). But you have to remember that HEAP SORT is not stable in comparison to MERGE SORT

Merge sort algorithm power point presentation

In this document

More Related Content

What's hot

Similar to Merge sort algorithm power point presentation

Recently uploaded

Merge sort algorithm power point presentation