# Class 27: Fast Sorting Algorithms

Held: Friday, 5 March 2004

Summary: Today we consider two important O(nlog2n) algorithms, merge sort and Quicksort.

Related Pages:

Assignments:

Notes:

• Are there questions on exam 2?

Overview:

• Merge sort.
• Quicksort.
• Lab.

## Faster Sorting Algorithms

• We saw in the problem of searching that it helps to apply the divide-and-conquer technique.
• That technique helped us design an O(log2n) searching algorithm.
• Can we apply the same technique to write a faster sorting algorithm?
• We'll consider two possible variants.

### Merge Sort

• We could simply split the pile into two equal halves. in two and sort the two halves.
• We then need to merge the two halves.
• So, let's think again about what we can do if we've sorted the two halves. How hard is it to put them together again?

### Quicksort

• One idea is to split the pile into two piles, one of big elements and one of small elements, sort the two subpiles, and combine them.
• That's a great idea, but it can be hard to decide what big and small mean.
• I'll show examples with a list of numbers.
• Because of the complexity of choosing how to split, we'll leave Quick Sort to CSC152 and CSC301.

## Lab

• You can explore these issues in more depth in the lab.
• Be prepared to reflect.

## 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 Fri May 7 09:43:18 2004.
The source to the document was last modified on Tue Jan 13 10:26:11 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Outlines/outline.27.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu