What is the advantage of top-down mergesort?Mergesort - Is Bottom-Up faster than Top-Down?Using mergesort with presorted intervalsMergesort OutOfMemoryErrorHow many times will merge and mergesort be run in mergesort algorithm?QuickSort for sorting part Mergesort?Top down mergesort. Merge operation not clearWhy is it necessary in the Merge-Sort algorithm to divide the array into two before sorting it?`std::list<>::sort()` - why the sudden switch to top-down strategy?infinite loop in divide part in mergeSortWhy does quicksort exclude the middle element but mergesort includes it?
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
Why doesn't H₄O²⁺ exist?
In Romance of the Three Kingdoms why do people still use bamboo sticks when paper had already been invented?
What killed these X2 caps?
Reserved de-dupe rules
Can one be a co-translator of a book, if he does not know the language that the book is translated into?
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
Do I have a twin with permutated remainders?
How could indestructible materials be used in power generation?
Took a trip to a parallel universe, need help deciphering
Can a virus destroy the BIOS of a modern computer?
What mechanic is there to disable a threat instead of killing it?
90's TV series where a boy goes to another dimension through portal near power lines
Infinite Abelian subgroup of infinite non Abelian group example
How to prevent "they're falling in love" trope
How can I prevent hyper evolved versions of regular creatures from wiping out their cousins?
What does it mean to describe someone as a butt steak?
Blender 2.8 I can't see vertices, edges or faces in edit mode
Today is the Center
Fully-Firstable Anagram Sets
Does a druid starting with a bow start with no arrows?
What exploit are these user agents trying to use?
Can I ask the recruiters in my resume to put the reason why I am rejected?
Why can't we play rap on piano?
What is the advantage of top-down mergesort?
Mergesort - Is Bottom-Up faster than Top-Down?Using mergesort with presorted intervalsMergesort OutOfMemoryErrorHow many times will merge and mergesort be run in mergesort algorithm?QuickSort for sorting part Mergesort?Top down mergesort. Merge operation not clearWhy is it necessary in the Merge-Sort algorithm to divide the array into two before sorting it?`std::list<>::sort()` - why the sudden switch to top-down strategy?infinite loop in divide part in mergeSortWhy does quicksort exclude the middle element but mergesort includes it?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
It seems like the divide step of recursive mergesort seems unnecessary. A bottom-up implementation that begins by splitting an array into a bunch of pairs and merging directly from there seems like it would always be preferable to dividing and merging recursively, as it would skip the splitting steps.
Is there any reason why top-down mergesort would be use and why it would be preferable / easier to implement than a bottom-up mergesort?
sorting
asked Mar 8 at 23:42
VastingVasting
6918
add a comment |
It seems like the divide step of recursive mergesort seems unnecessary. A bottom-up implementation that begins by splitting an array into a bunch of pairs and merging directly from there seems like it would always be preferable to dividing and merging recursively, as it would skip the splitting steps.
Is there any reason why top-down mergesort would be use and why it would be preferable / easier to implement than a bottom-up mergesort?
sorting
asked Mar 8 at 23:42
VastingVasting
6918
add a comment |
It seems like the divide step of recursive mergesort seems unnecessary. A bottom-up implementation that begins by splitting an array into a bunch of pairs and merging directly from there seems like it would always be preferable to dividing and merging recursively, as it would skip the splitting steps.
Is there any reason why top-down mergesort would be use and why it would be preferable / easier to implement than a bottom-up mergesort?
sorting
asked Mar 8 at 23:42
VastingVasting
6918
It seems like the divide step of recursive mergesort seems unnecessary. A bottom-up implementation that begins by splitting an array into a bunch of pairs and merging directly from there seems like it would always be preferable to dividing and merging recursively, as it would skip the splitting steps.
Is there any reason why top-down mergesort would be use and why it would be preferable / easier to implement than a bottom-up mergesort?
sorting
sorting
asked Mar 8 at 23:42
VastingVasting
6918
asked Mar 8 at 23:42
VastingVasting
6918
asked Mar 8 at 23:42
VastingVasting
6918
asked Mar 8 at 23:42
VastingVasting
6918
asked Mar 8 at 23:42
VastingVasting
6918
6918
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Assuming both are optimized and basic (not hybrid) versions of merge sort, there is a question if the size of an array is not a power of 2, then top down does better splits, but top down doesn't begin any merging until the recursive splitting produces two runs of size 1, so no gain there, and an imbalance in the size of sub-arrays doesn't affect overall performance as much as the overhead of recursively splitting the array and storing all those indexes on the stack. There's also the question of cache locality: for top down merge sort, when sub-array size is small enough, merged (output) data will still be in the cache and available as input for the next merge operation, but at the same time that merged data cache is also being accessed to flush it out to main memory.
The overhead of recursion for top down has time complexity O(log2(n)), while the total sort time complexity for both top down and bottom up merge sort is O(n log2(n)), so as the array size gets larger, the relative overhead of top down diminishes, as most of the time will be spent merging sub-arrays.
In all my benchmark tests, bottom up is always faster than top down, but by a relatively small amount for large arrays. On my system (Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015), for 16 million 64 bit unsigned integers, bottom up takes about 1.5 seconds, top down about 1.6 seconds.
Most actual libraries use some variation of bottom up merge sort, usually a hybrid combination of insertion sort for small sub-arrays (16 to 64 elements) and bottom up merge sort, such as TimSort. The size of the sub-array to use with insertion sort is chosen so that it takes an even number of mergesort passes, with the sorted data ending up in the original array.
This leaves top down merge sort as mostly a learning exercise, especially if it's being taught along with quicksort, which is also top down.
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55072511%2fwhat-is-the-advantage-of-top-down-mergesort%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Assuming both are optimized and basic (not hybrid) versions of merge sort, there is a question if the size of an array is not a power of 2, then top down does better splits, but top down doesn't begin any merging until the recursive splitting produces two runs of size 1, so no gain there, and an imbalance in the size of sub-arrays doesn't affect overall performance as much as the overhead of recursively splitting the array and storing all those indexes on the stack. There's also the question of cache locality: for top down merge sort, when sub-array size is small enough, merged (output) data will still be in the cache and available as input for the next merge operation, but at the same time that merged data cache is also being accessed to flush it out to main memory.
The overhead of recursion for top down has time complexity O(log2(n)), while the total sort time complexity for both top down and bottom up merge sort is O(n log2(n)), so as the array size gets larger, the relative overhead of top down diminishes, as most of the time will be spent merging sub-arrays.
In all my benchmark tests, bottom up is always faster than top down, but by a relatively small amount for large arrays. On my system (Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015), for 16 million 64 bit unsigned integers, bottom up takes about 1.5 seconds, top down about 1.6 seconds.
Most actual libraries use some variation of bottom up merge sort, usually a hybrid combination of insertion sort for small sub-arrays (16 to 64 elements) and bottom up merge sort, such as TimSort. The size of the sub-array to use with insertion sort is chosen so that it takes an even number of mergesort passes, with the sorted data ending up in the original array.
This leaves top down merge sort as mostly a learning exercise, especially if it's being taught along with quicksort, which is also top down.
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
add a comment |
Assuming both are optimized and basic (not hybrid) versions of merge sort, there is a question if the size of an array is not a power of 2, then top down does better splits, but top down doesn't begin any merging until the recursive splitting produces two runs of size 1, so no gain there, and an imbalance in the size of sub-arrays doesn't affect overall performance as much as the overhead of recursively splitting the array and storing all those indexes on the stack. There's also the question of cache locality: for top down merge sort, when sub-array size is small enough, merged (output) data will still be in the cache and available as input for the next merge operation, but at the same time that merged data cache is also being accessed to flush it out to main memory.
The overhead of recursion for top down has time complexity O(log2(n)), while the total sort time complexity for both top down and bottom up merge sort is O(n log2(n)), so as the array size gets larger, the relative overhead of top down diminishes, as most of the time will be spent merging sub-arrays.
In all my benchmark tests, bottom up is always faster than top down, but by a relatively small amount for large arrays. On my system (Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015), for 16 million 64 bit unsigned integers, bottom up takes about 1.5 seconds, top down about 1.6 seconds.
Most actual libraries use some variation of bottom up merge sort, usually a hybrid combination of insertion sort for small sub-arrays (16 to 64 elements) and bottom up merge sort, such as TimSort. The size of the sub-array to use with insertion sort is chosen so that it takes an even number of mergesort passes, with the sorted data ending up in the original array.
This leaves top down merge sort as mostly a learning exercise, especially if it's being taught along with quicksort, which is also top down.
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
add a comment |
Assuming both are optimized and basic (not hybrid) versions of merge sort, there is a question if the size of an array is not a power of 2, then top down does better splits, but top down doesn't begin any merging until the recursive splitting produces two runs of size 1, so no gain there, and an imbalance in the size of sub-arrays doesn't affect overall performance as much as the overhead of recursively splitting the array and storing all those indexes on the stack. There's also the question of cache locality: for top down merge sort, when sub-array size is small enough, merged (output) data will still be in the cache and available as input for the next merge operation, but at the same time that merged data cache is also being accessed to flush it out to main memory.
The overhead of recursion for top down has time complexity O(log2(n)), while the total sort time complexity for both top down and bottom up merge sort is O(n log2(n)), so as the array size gets larger, the relative overhead of top down diminishes, as most of the time will be spent merging sub-arrays.
In all my benchmark tests, bottom up is always faster than top down, but by a relatively small amount for large arrays. On my system (Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015), for 16 million 64 bit unsigned integers, bottom up takes about 1.5 seconds, top down about 1.6 seconds.
Most actual libraries use some variation of bottom up merge sort, usually a hybrid combination of insertion sort for small sub-arrays (16 to 64 elements) and bottom up merge sort, such as TimSort. The size of the sub-array to use with insertion sort is chosen so that it takes an even number of mergesort passes, with the sorted data ending up in the original array.
This leaves top down merge sort as mostly a learning exercise, especially if it's being taught along with quicksort, which is also top down.
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
Assuming both are optimized and basic (not hybrid) versions of merge sort, there is a question if the size of an array is not a power of 2, then top down does better splits, but top down doesn't begin any merging until the recursive splitting produces two runs of size 1, so no gain there, and an imbalance in the size of sub-arrays doesn't affect overall performance as much as the overhead of recursively splitting the array and storing all those indexes on the stack. There's also the question of cache locality: for top down merge sort, when sub-array size is small enough, merged (output) data will still be in the cache and available as input for the next merge operation, but at the same time that merged data cache is also being accessed to flush it out to main memory.
The overhead of recursion for top down has time complexity O(log2(n)), while the total sort time complexity for both top down and bottom up merge sort is O(n log2(n)), so as the array size gets larger, the relative overhead of top down diminishes, as most of the time will be spent merging sub-arrays.
In all my benchmark tests, bottom up is always faster than top down, but by a relatively small amount for large arrays. On my system (Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015), for 16 million 64 bit unsigned integers, bottom up takes about 1.5 seconds, top down about 1.6 seconds.
Most actual libraries use some variation of bottom up merge sort, usually a hybrid combination of insertion sort for small sub-arrays (16 to 64 elements) and bottom up merge sort, such as TimSort. The size of the sub-array to use with insertion sort is chosen so that it takes an even number of mergesort passes, with the sorted data ending up in the original array.
This leaves top down merge sort as mostly a learning exercise, especially if it's being taught along with quicksort, which is also top down.
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
answered Mar 9 at 0:43
rcgldrrcgldr
16k31436
16k31436
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55072511%2fwhat-is-the-advantage-of-top-down-mergesort%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
