Processing time of InsertionSort is c · n2. To merge k pre-sorted subarrays that

Question

Processing time of InsertionSort is c · n2. To merge k pre-sorted subarrays that contain together n items you have to compare the k top items in all the sub- arrays to choose the current maximum item and place it into the sorted array (assuming that all the items have to be sorted in ascending order). Therefore, the time for merging is proportional to (k 1) · n.

Let the processing time of the merge be c · (k 1) · n where the scale factor has the same value as for InsertionSort. Analyse whether it is possible to accelerate sorting of n items in the following way:

-Split the initial array of size n into k subarrays of size n/k. The last subarray may be longer to preserve the total number of items n but do not go in such details in your analysis.

-Sort each subarray separately by InsertionSort.

-Merge the sorted subarrays into a final sorted array.

If you have found that the acceleration is possible, then find the optimum value of k and compare the resulting time complexity of this sorting algorithm to that of InsertionSort and MergeSort.

Explanation / Answer

Answer: Let an array of size n be split into k subarrays of size n k . Then the total time to separately sort the subarrays is k · c · n k 2 = c · n 2 k . Time for merging k presorted subarrays is c · (k 1) · n. Thus the total time is proportional to n 2 k + n · (k 1). If k = 1 the sorting is O(n 2 ). If k = n the sorting is also O(n 2 ). This suggests that the computational complexity may be less somewhere in between these bounds.

Those who know the calculus may easily derive the optimum k by differentiating the expression n k + k 1 by k and setting it equal to zero: n k2 + 1 = 0, or k = n. Those who do not like mathematics may exploit the inverse symmetry between the terms n k and k in this sum. These terms have the fixed product n = n k · k, so they should be set equal for the optimum point: n k = k, or k = n. Both variants of getting the result are acceptable. The resulting time complexity of this sorting is O(n 1.5 ) so that the algorithm is better than InsertionSort but worse than MergeSort.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.