MERGE SORT with all case analysis and case

merge sort

1. DIVIDE AND CONQUER- MERGE SORT 1

2. 2 Divide-and-Conquer Divide The problem into a number of sub problems Conquer The sub problems by solving them recursively. If the sup problem sizes are small enough, however, just solve the sup problems in a straightforward manner Combine The solutions to the sub problems into the solution for the original problem

3. Divide-and-Conquer Technique (cont.) sub problem 2 of size n /2 sub problem 1 of size n /2 a solution to sub problem 1 a solution to the original problem a solution to sub problem 2 a problem of size n It general leads to a recursive algorithm! 3 3

4. DIVIDE AND CONQUER CAN BE SOLVED BY MEANS OF MASTER THEOREM 4

5. Divide-and-Conquer Examples Sorting: merge sort and quick sort Binary search Binary tree traversals Multiplication of large integers Matrix multiplication: Strassen’s algorithm Closest-pair and convex-hull algorithms 5 5

6. An Example: Merge Sort Sorting Problem : Sort a sequence of n elements into non-decreasing order. Divide : Divide the n -element sequence to be sorted into two subsequences of n/2 elements each Conquer: Sort the two subsequences recursively using merge sort. Combine : Merge the two sorted subsequences to produce the sorted answer. 6 6

7. Merge sort Algorithm Split array A[0.. n -1] into about equal halves and make copies of each half in arrays B and C Sort arrays B and C recursively Merge sorted arrays B and C into array A as follows: Repeat the following until no elements remain in one of the arrays: compare the first elements in the remaining unprocessed portions of the arrays copy the smaller of the two into A, while incrementing the index indicating the unprocessed portion of that array Once all elements in one of the arrays are processed, copy the remaining unprocessed elements from the other array into A. 7 7

8. Mergesort Example The non-recursive version of Mergesort starts from merging single elements into sorted pairs. 8

9. Merge Sort Perfect example of Divide-and-Conquer Strategy. It sorts a given array Arr[0,…,n-1] by dividing it into two halves Arr[0,……n/2 -1] and Arr[n/2,…..n-1] Each sub array is sorted recursively The resulting sub arrays are merged to produce a single sorted sub array of n elements. The fundamental operation in this algorithm is merging two sorted lists 9

10. Merging Step in Merge sort Consider two input arrays L and R to be merged to output array Arr Three counters i, j, k are initially set to the beginning of theirs respective arrays. The smaller of L[ i ] and R[ j ] is copied to the next entry of array Arr. Appropriate counters are advanced. When either of the input list is exhausted, the remainder of the other list is copied to array Arr 10

11. 11 Merge Sort

12. Merging – Example 12

13. Merging – Example 13

14. Pseudocode 14 //Sorts array A [0 ..n − 1] by recursive mergesort //Input: An array A[0..n − 1] of orderable elements //Output: Array A[0..n − 1] sorted in nondecreasing order ALGORITHM Merge-Sort (A[0…n-1], start, end) if start<end mid=(start+end)/2 Mergesort(A[], start, mid ) //Call for first half Mergesort(A[], mid+1, end) //Call for second half Merge(A[], start, mid, end) END

15. Cont… 15 ALGORITHM Merge(A[], start, mid, end)     n1 = mid - start + 1;     n2 =  end - mid; copy A[0..n/2 − 1] to Left[0..n1]   /* Copy data to temp arrays*/ copy A[n/2..n − 1] to Right[0..n2] i ←0; j ←0; k←start while i <n1 and j <n2 do if Left[i]≤ Right[j ] A[k]←Left[i]; i ←i + 1 else A[k]←Right[j ]; j ←j + 1 k←k + 1 End while copy Left[i … n1 − 1] to A[k … n1 + n2 − 1] copy Right[j ... n2 − 1] to A[k … n1 + n2 − 1] END // Merging the divided Array

16. Analysis of Merge Sort In merge sort algorithm, two recursive calls are made. Each call focuses on n/2 elements of the list. After 2 recursive calls, one call is made to combine the two sub lists. (To merge all n elements) Recurrence Relation : T(n) = T(n/2) + T(n/2) + n , n>1 T(1) = 0 , n=1 16

17. 17 Method 1

18. Sorting Technique Data structure Time complexity: Best Time complexity: Average Time complexity: Worst Quick sort Array O( n log( n )) O( n log( n )) O( n 2 ) Merge sort Array O( n log( n )) O( n log( n )) O( n log( n )) Bubble sort Array O( n ) O( n 2 ) O( n 2 ) Insertion sort Array O( n ) O( n 2 ) O( n 2 ) Selection sort Array O( n 2 ) O( n 2 ) O( n 2 ) Time complexity of all sorting techniques 18

19. THANKYOU !!! 19