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.

The Algorithm

Before going over the exercise we will use this section to briefely explain merge sort itself with an idea towards making the exercise easier to understand.

The Concept

An easy to follow diagram taken from Wikipedia

Merge Sort runs in the following way.

1. Divide the unsorted list in half creating two unsorted lists.
2. Divide each of these lists in half recursively until we have all lists of size one.
3. Merge these lists to create one sorted list.

There are two key ideas behind merge sort.

1. A smaller list is easier to sort than a large list.
2. Two lists that are already sorted are easier to merge into a sorted list than two unsorted lists.

Psuedocode

Heres a pseudocode version of mergesort. This is a two method implementation. The first method handles the dividing of the lists, the second is a merge method, it takes two lists and collapses them into one. The algorithm can easily be done with one method, but it complicates the code unnecessarily.

function mergesort(m)
    var list left, right, result
    if length(m) ≤ 1
        return m
    else
        var middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        return merge(mergesort(left), mergesort(right)

The merge algorithm can be done in many ways, this is a simple one.

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    if length(left) > 0 
        append rest(left) to result
    if length(right) > 0 
        append rest(right) to result
    return result

A full version of merge sort written in Java can be found here

The Exercise

The rest of this page is devoted to a learning exercise designed to help students understand Merge Sort.

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.