CODEWITHSUNDEEP
algorithmsortingmergesort
richardR
richardR

Reputation: 13

Modified MergeSort runtime

Help me to understand the runtime of the Modified MergeSort algorithm. In the classic MergeSort, when the input array is divided into two parts and sorted recursively, the execution time is: nlogn

What will be the execution time of the MergeSort algorithm if divide the input array into three parts (not half), recursively sort every third and finally merge the results using the three-argument Merge merge sub-program.

  1. n
  2. nlogn
  3. n (log n) ^ 2
  4. n ^ 2logn

Upvotes: 0

Views: 279

Answers (1)

chqrlie
chqrlie

Reputation: 145297

In the classic Merge Sort algorithm, there are approximately n * log2(n) comparisons and as many element copy operations, hence the time complexity of O(n.log(n)) because multiplicative constants are implicit.

If instead of splitting the array into 2 parts, you split into 3 parts, perform the same sort recursively on the parts and merge the 3 sorted slices into one, the number of comparisons increases to approximately 2 * n * log3(n) and the number of element copies is reduced to n * log3(n), but both are still proportional to n * log(n). Factoring out multiplicative constants, you still get a time complexity of O(n.log(n)).

Upvotes: 2

Related Questions