CSC 216/s08/prevent error
Formatting Resources
Formatting Help Guide from MetaWiki
Merge Sort
The underlying method of merge sort.
The problem
Merge sort is the quickest and most efficient of sorting methods, but it is run by an underlying concept that is not necessarily easy to grasp. It is our goal to make it more understandable.
Participants and props
This exercise can be done with any number of students. Preferably there should be ten or more students participating. No other props are required.
The script
We shall teach merge sort by sorting a group of students. There are many ways that students can be sorted, for this example we shall use height. A group of students should be arranged at the front of the room in a line. Follow the following steps.
- 1 Divide the line of students in two down the middle by moving the right half to the right and the left half to the left.
- 2 Using the left of the two new lines of students, check to see that the length is greater than 1, if so repeat steps one and two on this new line of students. If the size of the line reaches one, go to step three.
- 3 Having reached the smallest fracture of a line segment (ie both sides are one) or having two segments that are previously sorted, the two segments should be merged together. This is done by comparing shortest, or leftmost elements, the shortest is added to a new line, on the left, then the same comparison is made of the two shortest elements of the lists, and in this fashion the two lists are compiled together into one sorted list. This new list is then merged with the next sorted list. If the next list is as yet unsorted, repeat steps 1-2 on it until it is so.
- NOTE Merge sort can tend to be complicated, this explanation is not the best, and will hopefully be refined. A picture has been included to help with the process. The idea is to use merge sort on a line of students, explaining the steps along the way so has to help with comprehension of how merge sort works.