5/19

Sing, Prayer

ANNOUNCEMENTS
================
* No more Jazz announcements
* Homework #1 Due Today (in the box before the building closes)
* Lab 4 Assigned



OUTLINE
================
8.1 Why is Sorting Important?
8.2 Preliminaries
8.3 Insertion Sort
8.5 Mergesort
Lab 4 assigned
7.5.2-7.5.3 Divide-and-Conquer Running Times
Homework 1 due


GROUP WORK
==========
* 4 Groups
* Sort people by height, birthday using Insertion sort, Selection sort
* Mergesort

Selection Sort
======================

Insertion Sort (8.3)
======================
* An insertion sort is quadratic in the worst and average cases. It is fast if the input has already been sorted.

* An inversion measures unsortedness
* Example:   {8,5,9,2,6,3}
  inversions[10]: (8,5), (8,2), (8,6), (8,3), (5,2), (5,3), (9,2), (9,6), (9,3), (6,3)


Mergesort (8.5)
======================
* Mergesort uses divide-and-conquer to obtain an O(N log N) running time
* Merging of sorted arrays can be done in linear time
* Mergesort uses linear extra memory (twice the memory), which is a practical liability
* Excessive copying can be avoided with more work, but the linear extra memory cannot be removed without excessive time penalties


Lab 4
======================


Divide and Conquer Running Times (7.5.2-7.5.3)
===============================================