# Lab: Merge Sort

Summary: We consider a more efficient way to sort values.

Contents:

## Exercises

### Exercise 0: Preparation

a. Make a copy of mergesort.scm, my implementation of merge sort. Scan through the code and make sure that you understand all the procedures.

b. Start DrScheme.

### Exercise 1: Merging

a. Write an expresssion to merge the lists `(1 2 3)` and `(1 1.5 2.3)`.

b. Write an expression to merge two lists that contain the same values.

c. Write an expression to merge two lists of strings. (You may choose the strings yourself. Each list should have at least three elements.)

d. Assume that we represent names as lists of the form `(last-name first-name)`. Write an expression to merge the following two lists

```(define cs-faculty
(list (list "Bishop" "David")
(list "Gum" "Ben")
(list "Rebelsky" "Samuel")
(list "Stone" "John")
(list "Walker" "Henry")))

(define young-cs-kids
(list (list "Rebelsky" "Daniel")
(list "Rebelsky" "Jonathan")
(list "Rebelsky" "William")))
```

### Exercise 2: Reflecting on Merging

a. What will happen if you call `merge` with unsorted lists as the first two parameters?

c. What will happen if you call `merge` with sorted lists of very different lengths as the first two parameters?

### Exercise 3: Splitting

Use `split` to split:

a. A list of numbers of length 6

b. A list of numbers of length 5

c. A list of strings of length 6

### Exercise 4: Sorting

a. Run `merge-sort` on a list you design of fifteen integers.

b. Run `new-merge-sort` on a list you design of twenty strings.

c. Uncomment the lines in `new-merge-sort` that print out the current list of lists. Rerun `new-merge-sort` on a list you design of twenty strings. Is the output what you expect?

### Exercise 5: Special Cases

a. Run both versions of merge sort on the empty list.

b. Run both versions of merge sort on a one-element list.

c. Run both versions of merge sort on a list with duplicate elements.

### Exercise 6: Experimentally Comparing Sorts

a. Using DrScheme's built-in timing mechanism (you may have to look through the online help to find information about that mechanism), make a table of the running time of insertion sort, `merge-sort` and `new-merge-sort` on inputs of size 0, 10, 100, 1000, 10000, 20000, and 50000.

c. Based on your data, what can you say about the relative speeds of the three sorting methods?

## For Those with Extra Time

### Extra 1: Splitting, Revisited

One of my colleagues prefers to define `split` something like the following

```(define split
(lambda (ls)
(let kernel ((rest ls)
(left null)
(right null))
(if (null? rest)
(list left right)
(kernel (cdr rest) (cons (car rest) right) left)))))
```

a. How does this procedure split the list?

b. Why might you prefer one version of split over the other?

## History

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue Dec 9 13:59:09 2003.
The source to the document was last modified on Mon Nov 24 13:49:32 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003F/Labs/mergesort.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu