You are not logged in.
#26 2013-11-29 03:45:01 pm
- Nigel Garvey
- Moderator
- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 4807
Re: A merge sort
In view of the demise of ScriptBuilders, I've updated the scripts in posts #1 and #6 and rewritten the blurb in the latter.
NG
Offline
#27 2015-06-14 01:51:15 pm
- Nigel Garvey
- Moderator
- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 4807
Re: A merge sort
I've updated the scripts in the light of a tip I read on Wikipedia a couple of days ago that it's only necessary to extract separate lists of the left halves for the merges, not lists containing both halves. Quite a revelation eight years after I wrote the code!
NG
Offline
#28 2015-06-20 10:17:07 am
Re: A merge sort
That is nice. 
Still not been around to test it. The reason I reply here, is that I have an idea for testing a average cases of algorithms.
This can of course been done the hard way, by computing the complexity of the algorithm, and then working with the probability of the average number of inversions in a data set.
My idea, is to bluntly create a data set with an average number of inversions, which is misplaced elements with respect to the sorting order. Then time the implementation of the algorithm with this dataset.
The average number of inversions is (N(N-1))/4.
The whole proof of this can be found on page 431 in Rosen: "Discrete Mathematics with Applications" 6th Edition"
There is of course the math there for doing the average case computations, taking the computational complexity into account as well, if you need to compare average cases with varying algorithms and number of inputs.
Edit
An easier way to figure out the average number of unsorted number of elements, without coming up with a formal proof, given the 50% probability per element that it is either sorted or unsorted, and by the linearity of expectations, (that you can sum up expected values). the math should hold: The sum of the elements that are unsorted when we have 50% chance of "unsortedness" per element, should be the half of the number of elements on an average.)
So, in a set with N elements, there should be an average of N/2 unsorted elements, which seems quite intuitive, and that I remember having seen in writing earlier, now that I have computed it.
Last edited by McUsrII (2015-06-21 09:59:22 pm)
T.B
p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.
Offline
#29 2015-06-21 04:13:39 am
- DJ Bazzie Wazzie
- Member
- From:: the Netherlands
- Registered: 2004-10-20
- Posts: 2808
- Website
Re: A merge sort
The reason I reply here, is that I have an idea for testing a average cases of algorithms.
Good idea, but merge sort will not be affected how the data is shuffled like other sorting algorithms.
Offline
#30 2015-06-21 09:57:44 am
Re: A merge sort
Actually.
Not totally sure how they got n log n as a result, but if you add up the smaller terms, then you have to take the swap operations into account, which will wary with the number of operations.
T.B
p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.
Offline
#31 2015-06-21 06:05:16 pm
- DJ Bazzie Wazzie
- Member
- From:: the Netherlands
- Registered: 2004-10-20
- Posts: 2808
- Website
Re: A merge sort
Nigel's recursive merge sort (or iterative merge sort) requires an buffer where items from two lists are merged into one list. Inside the deepest recursive (or first iterative) call there are two lists each containing only 1 item and are merged into one list containing two items, this may look like swapping but it's not. The next iteration or parent handler it becomes much more different from swapping. The drawback of merge sort requiring additional temporary buffers, which is the real bottleneck in performance. There is no difference if an item is "swapped" or not, it's copied to the buffer before or after the the item in the opposite list is copied to the buffer.
Offline
#32 2015-06-21 10:00:47 pm
Re: A merge sort
Hello.
I did look at a text book implementation of a merge sort, which did swap elements if one element was larger than the next.
I probably should remove all those posts from this thread, and post it as a general subject in relation to timing, it seemed as a good idea at the time, since Nigel probably would be interested in the result, if he hadn't seen that way of overcoming the obstacle there is to compute the average case of a sorting algorithm.
Last edited by McUsrII (2015-06-21 10:11:25 pm)
T.B
p a file peruser, work in progress, but is sane, and lets you copy the file you view to the clipboard. Enter just "p" for help. Slightly better terminal handling, when executing shell commands from within.
Offline
#33 2015-06-22 03:37:23 am
- Nigel Garvey
- Moderator
- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 4807
Re: A merge sort
Nigel's recursive merge sort (or iterative merge sort) requires an buffer where items from two lists are merged into one list. Inside the deepest recursive (or first iterative) call there are two lists each containing only 1 item and are merged into one list containing two items, this may look like swapping but it's not. The next iteration or parent handler it becomes much more different from swapping. The drawback of merge sort requiring additional temporary buffers, which is the real bottleneck in performance. There is no difference if an item is "swapped" or not, it's copied to the buffer before or after the the item in the opposite list is copied to the buffer.
Hi DJ.
In my recursive merge sorts, each recursion extracts a shallow copy of a range in the main list and merges the two ends of the copy back to the original range. (The revision I made last week only extracts a copy of the left end of the range, merging from that and the right end of the original back to the original.) Where the range is only two items long, any rearrangement is done by swapping, not by recursion, extraction, and merging. The method does still produce a lot of temporary lists over the course of the sort, but only a third as many as the code published with the source from which learned the algorithm. One nice thing about merging a copy back to the original is that if the left items are exhausted first, the remaining right items must already be in the right places and needn't be copied back too.
My iterative merge sorts only use one additional list per sort, merging back and forth between this and the original list on alternate passes. The exception is the first pass, which handles the shortest ranges (two items each in the binary sorts or three in the ternary versions). These are dealt with by swapping in the original list. When merging back and forth between two lists, it's necessary to complete the merges even after the left items are exhausted.
Last edited by Nigel Garvey (2015-06-22 03:40:08 am)
NG
Offline
#34 2015-08-13 07:20:35 pm
- Shane Stanley
- Member
- From:: Australia
- Registered: 2002-12-07
- Posts: 5562
Re: A merge sort
The animations on this page might be of interest to lurkers:
www.sorting-algorithms.com
Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com
Offline
#35 2015-08-21 04:48:54 pm
- Nigel Garvey
- Moderator
- From:: Warwickshire, England
- Registered: 2002-11-20
- Posts: 4807
Re: A merge sort
Thanks, Shane. Those are fun to watch.
NG
Offline
