27700

Time complexity using N way Merge

Question:

I was going over the 2 way merge sort algorithm and was thinking if by reducing the merge passes can we get better gain in terms of time.

E.g in a 2 way merge we have the following recurrence:

T(n) = 2T(n/2) + O(n)

and this has a time complexity of N.log-base2(N)

if I divide the problem by 4 and merge 4 sub arrays I will get

T(n) = 4T(n/4) + O(n)

and this should have a time complexity of N.log-base4(N)

Since, the number of merge passes has reduced, should this be something to consider when implementing merge sort ?

e.g with an array of 64 elements the first approach will have 6 passes and using the second approach it will have 3 passes.

Edit:

Ok, so with 2T(n/2) we are doing N comparisons per pass and with 4T(n/4) we end up doing 3*N comparisons per pass ? What about the cost of moving elements to result arrary, does that remain same at each pass ?

Answer1:

Note that the base-4 log of a number is exactly half the base-2 log of a number; thus, you're only introducing a constant-factor speedup. Except you're not, because you introduce a similar constant-factor SLOWDOWN in the cost of the actual merging (2-way merge needs 1 comparison per item, 4-way may need up to 3). So while there may be fewer passes, the passes are each more costly. So you've complicated the code a fair bit, and the benefits are in question.

Answer2:

It sounds reasonable but is not, because in this case you have to do at least 5 comparions to sort each 4 elements. This way you have 5*N*log4(N) comparisons and this is greater than N*log2(N) by factor 5*log(2)/log(4)

Answer3:

Height of decomposition tree is log<sub>4</sub>n, but running time is not n log<sub>4</sub>n.

In first step you have four list of size n/4, their merge takes n/4 + n/4 + n/2 comparison. but in normal case it takes n/2 comparison, so you half the height of tree but you multiply each merge with two, so total running time is not better than division to 2 part. (you can prove for other depths of tree that you should have at least two times comparison compare to tree with two branch).

<hr />

<em>P.S:By running time I mean number of comparison.</em>

Recommend

  • Is there a benefit to using Encoded Polylines with Google Maps API v3? [closed]
  • Sorting a dictionary by an inner “attribute” dictionary key-value
  • What is the best way to insert only month, day and time in database table?
  • ANOVA on multiple responses, by multiple groups NOT part of formula
  • Where to put clearQueue in jQuery code
  • How to get value of the slider, when touchend or mouseup events are used?
  • How can I merge my files when the folder structure has changed using Borland StarTeam?
  • Simple Factory with reflection C#
  • Build Matrix of Comparisons in SQl Server
  • Neo4j: Filter nodes based on aggregate function
  • A class implementing two different IObservables?
  • Divide a $1 by 3 and adjusting 1 cent
  • Recording values of radio buttons in ember
  • Activation Function choice for Neural network
  • JSR-330 support in Picocontainer : @Inject … @Named(\"xxx)
  • Creating a DropDownList
  • Who propagate bugfixes across branches (corporate development)?
  • Firefox Extension - Monitor refresh and change of tab
  • Tamper-proof configuration files in .NET?
  • Create DicomImage from scratch using Dcmtk
  • How to do unit test for HttpContext.Current.Server.MapPath
  • Scrapy recursive link crawler
  • Fetching methods from BroadcastReceiver to update UI
  • Why HTML5 Canvas with a larger size stretch a drawn line?
  • Why doesn't :active or :focus work on text links in webkit? (safari & chrome)
  • Symfony2: How to get request parameter
  • When should I choose bucket sort over other sorting algorithms?
  • Timeout for blocking function call, i.e., how to stop waiting for user input after X seconds?
  • Rearranging Cells in UITableView Bug & Saving Changes
  • GridView Sorting works once only
  • Numpy divide by zero. Why?
  • php design question - will a Helper help here?
  • Unanticipated behavior
  • AngularJs get employee from factory
  • WPF Applying a trigger on binding failure
  • Benchmarking RAM performance - UWP and C#
  • Angular 2 constructor injection vs direct access
  • How does Linux kernel interrupt the application?
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • Authorize attributes not working in MVC 4