StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><code>__merge_without_buffer()</code> is performing an <strong>in-place merge</strong>, as the merge step of an in-place merge sort. It takes as input two ranges of data <code>[first, middle)</code> and <code>[middle, last)</code> which are assumed to already be sorted. The <code>len1</code> and <code>len2</code> parameters are equal to the lengths of the two input ranges, namely <code>(middle - first)</code> and <code>(last - middle)</code> respectively.</p> <p>First, it picks a <em>pivot</em> element. Then, it rearranges the data into the order <code>A1 B1 A2 B2</code>, where <code>A1</code> is the set of elements in <code>[first, middle)</code> that are less than the pivot, <code>A2</code> is the set of elements in <code>[first, middle)</code> greater than or equal to the pivot, <code>B1</code> is the set of elements in <code>[middle, last)</code> less than the pivot, and <code>B2</code> is the set of elements in <code>[middle, last)</code> greater than or equal to the pivot. Note that the data is originally in the order <code>A1 A2 B1 B2</code>, so all we need to do is to turn <code>A2 B1</code> into <code>B1 A2</code>. This is with a call to <code>std::rotate()</code>, which does just that.</p> <p>Now we've separated out the elements which are less than the pivot (<code>A1</code> and <code>B1</code>) from those that are greater than or equal to the pivot (<code>A2</code> and <code>B2</code>), so now we can recursively merge the two subranges <code>A1 A2</code> and <code>B1 B2</code>.</p> <p>How do we choose a pivot? In the implementation I'm looking at, it chooses the median element from the larger subrange (i.e. if <code>[first, middle)</code> has more elements than <code>[middle, last)</code>, it chooses the median of <code>[first, middle)</code>; otherwise, it chooses the median of <code>[middle, last)</code>). Since the subranges are already sorted, choosing the median is trivial. This pivot choice ensures that when recursively merging the two subranges, each subproblem is no more than 3/4 the size of the current problem, because in the worst case, at least 1/4 of the elements are larger than or smaller than the pivot.</p> <p>What is the running time of this? The <code>std::rotate()</code> call takes O(N) time, and we make two recursive calls to ourselves. This equates to a running time of O(N log N). However, note that this is only one step in mergesort: remember that in mergesort you first recursively sort both halves and then merge. Thus, the recurrence relation for the running time of mergesort is now:</p> <p><code>T(N) = 2T(N/2) + O(N log N)</code></p> <p>Plug this into the <a href="http://en.wikipedia.org/wiki/Master_theorem" rel="noreferrer">Master theorem</a>, and you get that mergesort now runs in O(N log<sup>2</sup> N) time!</p> <p>As an interesting final point, consider the following three qualities of a comparison-based sorting algorithm:</p> <ol> <li>In-place</li> <li>Stable</li> <li>Runs in O(N log N) time</li> </ol> <p>You can usually only get 2 of these at once - quicksort gets you (1) and (3), mergesort gets you (2) and (3), and an in-place mergesort gets you (1) and (2). Non-comparison-based sorts such as count sort can achieve all 3, but those sorts can only sort certain data types. It's possible there exists a comparison-based sort which achieves all 3, but if there is, I'm not aware of its existence, and it's almost certainly much more complicated.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload