Api 610 latest edition

C++ Merge and Heap Sorts © 2001 B. Tjaden 1SortingAsymptotic Growth Ratelet’s look at the running time of several algorithms for the same problem 1Algorithm1234Time Function in Microsecs33n46nlogn13n23.4n3Input Size nSolution Time10.00033 sec.0015 sec.0013 sec.0034 sec100.003 sec.03 sec.13 sec3.4 sec1,000.033 sec.45 sec13 sec.94 hr10,000.33 sec6.1 sec22 min39 days100,0003.3 sec1.3 min1.5 days108 yrhigh constant factors on Θ(n) and Θ(nlogn) do not make them slower that other algorithms except for very small inputsthe running time increases asymptotically as input size increasesasymptotic growth rates are denoted by the Greek symbol ΘMerge Sortslices the array into 2 halvessorts the halves separatelydivide and conquerthe idea is to sort each half of the array recursively, with smaller and smaller numbers of elementAis the arrayfirstis the index of the first element of the arraylastis the last element of the array1Programming Pearlsby Jon Bentley, Addison-Wesley, Reading, Mass, 1986
C++ Merge and Heap Sorts © 2001 B. Tjaden 2void mergeSort(Element [] A, int first, int last){if(first < last){int mid = (first+last)/2;mergeSort(A,first,mid);mergeSort(A,mid+1,last);merge(A,first,mid,last);}// end if}merge(A,first,mid,last){Element B[last+1];int first1 = first;int last1 = mid;int first2 = mid+1;int last2 = last;// while both subarrays have more elements// copy the smaller element into temporary array Bint index = first1;for( ;(first1 <= last1) && (first2 <= last2); index++){if(A[first1] < A[first2]){B[index] = A[first1];first1++;}else{B[index] = A[first2];first2++;}//end if else} // end for// finish off non-empty array// if first array is not emptyfor( ; first1 <= last 1; ++first1,++index)B[index] = A[first1];// if second array is not emptyfor( ; first2 <= last 2; ++first2,++index){B[index] = A[first2];}// copy thearray B back into the original array Afor(index = first; index <= last; index++)A[index] = B[index];} // end merge