[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

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**

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

- 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.

- 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 + 2
^{k}*f(n/2^{k})

- f(n) = kn + 2
- When k = log
_{2}n- f(n) = nlog
_{2}n + n*1

- f(n) = nlog
- Therefore, f(n) is in O(nlog
_{2}n).

- We can also use a somewhat nontraditional analysis technique.
- Assume that we're dealing with n = 2
^{x}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)).

- 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).

- 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?

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

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.

[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

**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