Mergesort for big arrays/vectors
Do I sort the whole array in one go?
or sort bit by bit
1.sort 1000 elements
2.merge each sections together
or sort bit by bit
1.sort 1000 elements
2.merge each sections together
What you'll likely want to do is a nested for-loop and sort the whole array in one go. There's no point in sorting a little bit and then coming back to it later.
The whole point of a merge sort is that it is divide-and-conquer.
This makes it ideal for conditions where, for example, you do not have enough working memory to fit the entire array (such as huge disk files, or tapes stored in the server room, or if you are working on a micro-controller in some small device).
If you are being asked to do a merge sort (for homework?) then you should have been given some direction about it, either notes about its function or a good idea how to google for information on one.
A merge sort is conceptually simple but not so simple to implement, mainly because it takes some thinking to manage the auxiliary memory you need.
What have you got so far?
This makes it ideal for conditions where, for example, you do not have enough working memory to fit the entire array (such as huge disk files, or tapes stored in the server room, or if you are working on a micro-controller in some small device).
If you are being asked to do a merge sort (for homework?) then you should have been given some direction about it, either notes about its function or a good idea how to google for information on one.
A merge sort is conceptually simple but not so simple to implement, mainly because it takes some thinking to manage the auxiliary memory you need.
What have you got so far?
big is much bigger than you think.
my silly shell sort can do 6 million subsecond on a sub-par laptop single threaded.
sorting stuff that is very large in multiple threads and doing a dumb merge (this isnt merge sort, this is take the smallest off the top of the sorted sub-arrays in a loop until all are consumed, its just merge not mergsort in other words) can be better than std::sort but not until you get to gigantic chunks of data. std::sort is more than fine for a billion items on modest hardware, and depending on your performance needs, possibly multiples of that (at what point are you annoyed, 10 seconds? 30? 10 min?).
I would not advice splitting up an array until at least 1B items, unless you have some really weird special application (or are on a very weak embedded device, not a computer?!).
The comments about the purpose of mergesort above apply also ... out of memory, whatever issues. But those issues .... take a very large problem today (its easy to contrive something that needs it, of course). If you do decide you need to mergesort something, 1000 at a time is too small -- get as big a chunk as you can afford, which is likely millions even on limited hardware.
my silly shell sort can do 6 million subsecond on a sub-par laptop single threaded.
sorting stuff that is very large in multiple threads and doing a dumb merge (this isnt merge sort, this is take the smallest off the top of the sorted sub-arrays in a loop until all are consumed, its just merge not mergsort in other words) can be better than std::sort but not until you get to gigantic chunks of data. std::sort is more than fine for a billion items on modest hardware, and depending on your performance needs, possibly multiples of that (at what point are you annoyed, 10 seconds? 30? 10 min?).
I would not advice splitting up an array until at least 1B items, unless you have some really weird special application (or are on a very weak embedded device, not a computer?!).
The comments about the purpose of mergesort above apply also ... out of memory, whatever issues. But those issues .... take a very large problem today (its easy to contrive something that needs it, of course). If you do decide you need to mergesort something, 1000 at a time is too small -- get as big a chunk as you can afford, which is likely millions even on limited hardware.
Last edited on
Heh, yeah. If you are dealing with Big(er than working memory) then you are going to have to write a special-purpose sort. I didn't mean you needed to worry about any of that... (sorry).
As jonnin said, you have plenty of memory to work with.
Pick a sort strategy: bottom-up or top-down; both are about as easy. Top-down is the version usually taught first, and is probably what is wanted.
I recommend you allocate all the auxiliary memory you need once, at the top-level function, and simply pass it along to your recursive function. (You need half-round-up of the size of your array to sort.)
Your recursive function should:
• check bounds for recursion
• recurse if necessary
• copy the front half of the sort interval to the auxiliary memory
• merge auxiliary and back half back into the interval
Hope this helps.
As jonnin said, you have plenty of memory to work with.
Pick a sort strategy: bottom-up or top-down; both are about as easy. Top-down is the version usually taught first, and is probably what is wanted.
I recommend you allocate all the auxiliary memory you need once, at the top-level function, and simply pass it along to your recursive function. (You need half-round-up of the size of your array to sort.)
Your recursive function should:
• check bounds for recursion
• recurse if necessary
• copy the front half of the sort interval to the auxiliary memory
• merge auxiliary and back half back into the interval
Hope this helps.
Topic archived. No new replies allowed.