PROBLEM STATEMENT: Write a modular program using object oriented programming features to implement mergesort methods using Python. AIM: To mergesort method and its implementation. FACILITIES (TOOLS USED):Linux Operating System, Turbo C++, Eclipse Framework. ALGORITHM: MergeSort (A, low, high) if low <high // at least two elements mid (low + high) / 2 // divide the list into two halves ← MergeSort(A, low, mid) MergeSort(A, mid + 1, high) Merge(low, mid, high) end MergeSort. Merge(A[0..n 1], low, mid, high) – Semi sorted Array A Output: Merged sorted array A from low to high is for the first sublist i h← low // i ← + 1 // is for the second sublist j ← mid j while <mid and do // sublists not exhausted yet h j<high if <A[j] A[h] B[i]← A[h] + 1 h h ← else B[i]← A[j] + 1 j ←j + 1 i ←i >mid // first sublist exhausted copy remaining elements. if h – for to do k← j high B[i]← A[k] + 1 i ←i + 1 k k ← else // second sublist exhausted - copy remaining elements. for to do k← h mid B[i]← A[k] + 1 i ←i + 1 k k ← // Copy to B A for to do k← low high A[k]← B[k] + 1 k k ← end Merge. THEORY: To sort .. A[p r]: Divide Step If a given array has zero or one element, simply return; it is already sorted. Otherwise, A splitA[p .. into two subarrays .. and + 1 .. each containing about half of the r] A[p q] A[q r], elements of .. That is, is the halfway point of .. A[p r]. q A[p r]. 2. Conquer Step Conquer by recursively sorting the two subarrays .. and + 1 .. A[p q] A[q r]. Combine Step
PROBLEM STATEMENT: Write a modular program using object oriented programming features to implement mergesort methods using Python. AIM: To mergesort method and its implementation. FACILITIES (TOOLS USED):Linux Operating System, Turbo C++, Eclipse Framework. ALGORITHM: MergeSort (A, low, high) if low <high // at least two elements mid ← (low + high) / 2 // divide the list into two halves MergeSort(A, low, mid) MergeSort(A, mid + 1, high) Merge(low, mid, high) end MergeSort. Merge(A[0..n – 1], low, mid, high) Semi sorted Array A Output: Merged sorted array A from low to high i ← h← low // i is for the first sublist j ← mid + 1 // j is for the second sublist while h <mid and j<high do // sublists not exhausted yet if A[h] <A[j] B[i]← A[h] h ← h + 1 else B[i]← A[j] j ←j + 1 i ←i + 1 if h >mid // first sublist exhausted – copy remaining elements. for k← j to high do B[i]← A[k] i ←i + 1 k ← k + 1 else // second sublist exhausted - copy remaining elements. for k← h to mid do B[i]← A[k] i ←i + 1 k ← k + 1 // Copy B to A for k← low to high do A[k]← B[k] k ← k + 1 end Merge. THEORY: To sort A[p .. r]: Divide Step If a given array A has zero or one element, simply return; it is already sorted. Otherwise, splitA[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r]. 2. Conquer Step Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r]. Combine Step