31981

Merge sort space and time complexity

Question:

Given the following merge sort algorithm :

mergesort(A,p,r) if (r <= l) return //constant amount of time int m = (p+r)/2 //constant amount of time mergesort(A, p, q) // these two calls will decide the mergesort(A, q+1, r) // O(logn) factor inside O(n * logn) right? merge(A, p, q, r) lets dwell further merge(a,p,q,r){ n1 = q-p+1 //constant time n2 = r-q //constant time // Let L[1...n1+1] and R[1...n2+1] be new arrays // idk , lets say constant for i,j in L[],R[] L[i] = A[p+i-1] R[j] = A[q+j] // shouldn't this take time varying on size of array? // also extra space too? i=1 j =1 // constant time for k = p to r // everything below this will contribute to O(n) // inside O(n*logn) amirite? if L[i]<=R[j] A[k] = L[i] i++ else A[k] = R[j] j++

How come we are estimating O(nlogn) time complexity for it , keeping in mind that there are left and right arrays being created to be merged back?

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n, because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

Answer1:

I suggest you reason about this by drawing a tree on paper: first write down your whole array:

2 4 7 1 4 6 2 3 7 ...

Then write what the recursion causes it to be split in below it:

2 4 7 1 3 4 6 2 3 7 ... | 2 4 7 1 3 4 6 2 3 7 ... | | 2 4 7 1 3 4 6 2 3 7

And so on with each piece.

Then, count how many rows you've written. This will be close to the base 2 logarithm of the number of elements you started with (O(log n)).

Now, how much work is being done for each row? It's O(n). Merging two arrays of lengths n1, n2 will take O(n1 + n2), even if you have to allocate space for them (and you don't in a proper implementation). Since each row in the recursion tree has n array elements, it follows that the work done for each row is O(n) and therefore the entire algorithm is O(n log n).

<blockquote>

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n , because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

</blockquote>

This is more interesting. If you do indeed create new L, R arrays at each recursion step, then the space complexity will be O(n log n). But you don't do that. You create one extra array of size n at the beginning (think of it as a global variable), and then you store the result of each merge into it.

You only pass around things that help you identify the subarrays, such as their sizes and the indexes they begin at. Then you access them using the original array and store the result of the merge in the globally allocated array, resulting in O(n) extra space:

global_temp = array of size equal to the array you're sorting merge(a,p,q,r){ i=p j =q // constant time while i < q and j <= r // or a similar condition if A[i]<=A[j] global_temp[k++] = A[i] i++ else global_temp[k++] = A[j] j++ // TODO: copy remaining elements into global_temp // TODO: copy global_temp into A[p..r]

Answer2:

Your question is unclear, but perhaps you are confused by the extra space you need.

Obviously, on the first pass (and every pass) you read the entire data, and merge each partition into one twice as big.

Let's just focus on 8 elements.

8 7 6 5 4 3 2 1

In the first pass, the size of each partition is 1, and you are merging them to size=2. So you read the 8 and the 7, and merge them into a partition:

7 8 5 6 3 4 1 2

The next stage is to merge groups of 2 into groups of 4. Obviously, you have to read every element. So both of these passes take O(n) operations. The number of times to double is log2(n), which is why this algorithm is O(n log n)

In order to merge, you need extra room. You could recycle it. But the worst case is when you merge two n/2 partitions into n (the last time). The easy way to envision that is to allocate a buffer big enough to copy the entire data into. That would be O(n) storage.

5 6 7 8 1 2 3 4 i j EMPTY Buffer int buf[8] k = 0 buf[k++] = (orig[j] < orig[i]) ? orig[j++] : orig[k++]

Recommend

  • SonarQube Coverage for Branch
  • angular 2 pass array to custom validator (Template driven form)
  • Google play developer console crash reports
  • Unit test the Automapper profiles
  • How do i reset the geo-location service settings each time my page loads with HTML5 and Javascript
  • Restric firesotre CRUD to users within a specific domain
  • libgit2 with libssh2 and libopenssl on windows
  • Handle loading of .net module into PowerShell
  • Cannot read property “length” from undefined. (line 39, file “Code”)
  • Flask-Admin batch action with form
  • MQL4, Code layout for big EA
  • Issue with java String and String Builder
  • php7 session_start() times out page
  • combining pandas dataframes of different sampling rates
  • Find a directory using wildcard in Inno Setup
  • How to concatenate data.frame inside lists by using names?
  • Migrating MOSS 2007 from SQL 2000 to SQL 2005 [closed]
  • iterating through image folder using javascript and adding the result in HTML
  • Call a specific instance of a service in Azure Service Fabric
  • Newtonsoft.json serializing and deserializing base/inheirited where classes are from shared projects
  • Interactive labeling of images in jupyter notebook
  • Microsoft bot framework webchat C#
  • Spring Mvc submit/delete checked (selected) records from table
  • Specify the _id field using Bulk.IndexMany in ElasticSearch
  • Octave code for gradient descent using vectorization not updating cost function correctly
  • Detect when MathJax has finished loading in UIWebView
  • getting the values of checkboxes in a checkboxlist control
  • Finding all XML nodes between each two processing instructions
  • Git for windows has stopped working
  • mssql script data insert or update
  • Python sum values in tuple in a list in a dictionary?
  • Generate a runnable jar and include libraries in it with Maven
  • VS2010: Ctrl-PgUp / -PgDown like in browsers
  • Use 2D Text into 3D scenes in JavaFX results in blurry texts
  • jQuery colorbox breaks postbacks in ASP.NET Web Forms
  • Defer unused CSS
  • git clone, upload-pack out of memory
  • opencv deskewing a contour
  • time column in sqlite using gorm
  • Drag and drop unicode TText in DelphiXe4