MergeSort in data structure and its applications.pptx

MergeSort as a divide and conquer technique

1. Data Structure

2. Merge Sort https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/ Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.

3. Merge Sort Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order.

4. Merge Sort A[p . . . q] is an array, where n= q-p+1. If p is greater than or equal to q (p ≥ q) then the sub array has at most one element . Merge-sort(A[], p, q) If p ≥ q then return p; else mid= ( p+q )/2 Merge-sort(A[], p, mid) Merge-sort(A[], mid+1, q) Merge(A[], p, mid, mid+1, q)

5. Merge Sort void merge(int * Arr , int start, int mid, int end) { // create a temp array int temp[end - start + 1]; // crawlers for both intervals and for temp int i = start, j = mid+1, k = 0; // traverse both arrays and in each iteration add smaller of both elements in temp while( i <= mid && j <= end) { if( Arr [ i ] <= Arr [j]) { temp[k] = Arr [ i ]; k += 1; i += 1; } else { temp[k] = Arr [j]; k += 1; j += 1; } }

6. Merge Sort // add elements left in the first interval while( i <= mid) { temp[k] = Arr [ i ]; k += 1; i += 1; } // add elements left in the second interval while(j <= end) { temp[k] = Arr [j]; k += 1; j += 1; } // copy temp to original interval for( i = start; i <= end; i += 1) { Arr [ i ] = temp[ i - start] } }

7. Merge Sort Have we reached the end of any of the arrays? No: Compare current elements of both arrays Copy smaller element into sorted array Move pointer of element containing smaller element Yes: Copy all remaining elements of non-empty array

8. Merge Sort

9. Merge Sort https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/