# Class 29: More Efficient Sorting Algorithms

Back to Some Sorting Algorithms. On to Quicksort.

Held Friday, October 13, 2000

Summary

Today we visit our first divide-and-conquer sorting algorithm, merge sort.

Notes

• Exam 3 is ready.
• I'll use the last fifteen minutes of today's class for a final pre-break discussion of the project.
• No outline for today yet, sorry. (I'll write it during break.)

Overview

## Sorting with Divide and Conquer

• In the previous class, we identified a number of interesting sorting algorithms which took O(n2) time.
• Can we do better? Well, sometimes using divide-and-conquer helps speed up algorithms (in our experience from O(n) to O(log2n)).
• We'll look at two different ways of ``splitting'' the array.

### Merge Sort

• We can develop a number of sorting techniques based on the divide and conquer technique. One of the most straightforward is merge sort.
• In merge sort, you split the list, array, collection or ... into two parts, sort each part, and then merge them together.
• Unlike the previous algorithms, merge sort requires extra space for the sorted arrays or subarrays.
• We'll write this as a non-inplace routine which returns a new, sorted array, rather than sorting the existing array.

#### Running Time

• What is the running time?
• We can use recurrence relations:
• Let f(n) be the running time of merge sort on input of size n.
• f(1) = 1
• f(n) = n + 2*f(n/2)
• Let's run this for a few steps
• f(n)
• = n + 2*f(n/2)
• = n + 2*f(n/2)
• = n + 2*(n/2 + 2*f(n/2/2))
• = n + n + 4*f(n/4)
• = n + n + 4*(n/4 + 2*f(n/4/2))
• = n + n + n + 8*f(n/8)
• Generalizing
• f(n) = kn + 2k*f(n/2k)
• When k = log2n
• f(n) = nlog2n + n*1
• Therefore, f(n) is in O(nlog2n).

#### Running Time, Revisited

• We can also use a somewhat nontraditional analysis technique.
• Assume that we're dealing with n = 2x for some x.
• Consider all the sorts of `Array`s of size k as the same "level".
• There are n/k `Array`s of size k.
• Because we divide in half each time, there are log_2(n) levels.
• Going from level k to level k+1, we do O(n) work to merge.
• So, the running time is O(n*log_2(n)).

#### A Problem

• Unfortunately, merge sort requires significantly more memory than do the other sorting routines (you can spend some time trying to come up with an ``in place'' merge sort, but you are quite likely to fail).

#### Other Versions

• We've written merge sort so that it does not affect the original array.
• How might we write it so that it creates a sorted array?
• Will that save space?

### Splitting via Size

• Suppose we split the array into small and large elements.
• How does that affect everything?
• Think about it.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Monday, 24 October 2000

• Filled in the details (a little late).

Back to Some Sorting Algorithms. On to Quicksort.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Outlines/outline.29.html

Source text last modified Wed Oct 25 10:05:37 2000.

This page generated on Fri Oct 27 08:20:01 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu