Merge sort as folk dance
Merge sort as folk dance
Written by Mike James   
Sunday, 24 April 2011

The sort of the dance has now reached Merge Sort and it's very tricky - how does it end up with the boy-girl pairing?

Yes the team from Sapientia University is still dancing sort algorithms but no sign of a Quicksort just yet, even though it has been promised. If you would like to see their original four sorting dances then see Sorting algorithms as dances. This time we have a merge sort for you to follow.

In a Merge store the list is recursively divided into two lists until you reach a list consisting of one element (dancer) and then each list is merged to produce a list twice its size by taking the the elements from pairs of sub-lists in order. So if you have two lists [5] and [3] you take the 3 and then the 5 to give the list [3,5]. If you then have two lists [3,5] and {2,8] you take the 2 from the second list, then the 3 from the first list, then the 5 from the first and the 8 from the second to give [2,3,5,8] and so on.

The merge is much easier to see when you have two big partially sorted lists which is what happens near the end of the dance when the boys merge with the girls - how was that worked out! And more to the point how is it that in the final merge each boy ends up with a girl? 

 

mergesortdance

 

Ah such is the complexity and surrealism that is the sort of the dance....

 

        

If you would like to find out the details of merge sort from a programmer's perspective then see: Magic of Merging.

We wait patiently for the Quicksort but still don't think it is danceable....

Update 2nd May 2011

They have proved me wrong .... all it need for Quicksort as a Hungarian dance is a pair of hats:
At last - Quicksort the dance

Further Reading:

Sorting algorithms as dances

Silverlight Sorting Lab

SilverSort

Magic of Merging

QuickSort exposed

Sequential storage

 

Banner


MathML 3.0 Is An International Standard
03/07/2015

The story of MathML is not a happy one. It is a good idea - create a markup language for mathematical equations - but for some reason people just don't seem to want to get behind it.  Will the ne [ ... ]



Robocup 2015 Winners
25/07/2015

A total of 175 robot teams from 47 different countries and regions took part in this year's RoboCup held in the eastern Chinese city of Hefei. Teams from Japan, China, Iran, the USA and Aust [ ... ]


More News

Last Updated ( Tuesday, 03 May 2011 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2015 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.