CS210 · Sorting · Annotated SlidesMerge Sort
Original
Overview

Merge Sort

Mergesort: merging, the recursive top-down sort and bottom-up version, its N log N analysis and extra memory, comparators, and stability.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 40 slides
  1. 1 A l g o r i t h m s
  2. 2 Two classic sorting algorithms: mergesort and quicksort
  3. 3 Slide 3
  4. 4 w.SI
  5. 5 Abstract in-place merge demo
  6. 6 Abstract in-place merge demo
  7. 7 a 5 7
  8. 8 only
  9. 9 Mergesort: trace
  10. 10 Mergesort: animation
  11. 11 Mergesort: animation
  12. 12 Mergesort: empirical analysis
  13. 13 Mergesort: number of compares
  14. 14 Divide-and-conquer recurrence: proof by picture
  15. 15 Divide-and-conquer recurrence: proof by induction
  16. 16 Mergesort: number of array accesses
  17. 17 Mergesort analysis: memory
  18. 18 Java 6 system sort
  19. 19 Slide 19
  20. 20 Bottom-up mergesort
  21. 21 Bottom-up mergesort: Java implementation
  22. 22 Mergesort: visualizations
  23. 23 Sort countries by gold medals
  24. 24 Sort countries by total medals
  25. 25 Sort music library by artist
  26. 26 Sort music library by song name
  27. 27 Comparable interface: review
  28. 28 Comparator interface
  29. 29 Comparator interface: system sort
  30. 30 Comparator interface: using with our sorting libraries
  31. 31 Comparator interface: implementing
  32. 32 Comparator interface: implementing
  33. 33 Slide 33
  34. 34 Stability
  35. 35 Stability
  36. 36 Stability: insertion sort
  37. 37 Stability: selection sort
  38. 38 Stability: mergesort
  39. 39 Stability: mergesort
  40. 40 Sorting summary
Slide 1 / 40

A l g o r i t h m s

Slide 1: A l g o r i t h m s
Slide 2 / 40

Two classic sorting algorithms: mergesort and quicksort

Slide 2: Two classic sorting algorithms: mergesort and quicksort

Notes

  1. Mergesort: sort each half recursively, then merge.

Slide 3 / 40

Slide 3

Slide 3: Slide 3
Slide 4 / 40

w.SI

Slide 4: w.SI
Slide 5 / 40

Abstract in-place merge demo

Slide 5: Abstract in-place merge demo
Slide 6 / 40

Abstract in-place merge demo

Slide 6: Abstract in-place merge demo
Slide 7 / 40

a 5 7

Slide 7: a 5 7
Slide 8 / 40

only

Slide 8: only
Slide 9 / 40

Mergesort: trace

Slide 9: Mergesort: trace
Slide 10 / 40

Mergesort: animation

Slide 10: Mergesort: animation
Slide 11 / 40

Mergesort: animation

Slide 11: Mergesort: animation
Slide 12 / 40

Mergesort: empirical analysis

Slide 12: Mergesort: empirical analysis
Slide 13 / 40

Mergesort: number of compares

Slide 13: Mergesort: number of compares

Exam angle

PredictionQ1

Mergesort’s running time in the worst case is:

Slide 14 / 40

Divide-and-conquer recurrence: proof by picture

Slide 14: Divide-and-conquer recurrence: proof by picture
Slide 15 / 40

Divide-and-conquer recurrence: proof by induction

Slide 15: Divide-and-conquer recurrence: proof by induction
Slide 16 / 40

Mergesort: number of array accesses

Slide 16: Mergesort: number of array accesses
Slide 17 / 40

Mergesort analysis: memory

Slide 17: Mergesort analysis: memory

Exam angle

PredictionQ1

Standard mergesort sorts in place with constant extra memory.

Slide 18 / 40

Java 6 system sort

Slide 18: Java 6 system sort
Slide 19 / 40

Slide 19

Slide 19: Slide 19
Slide 20 / 40

Bottom-up mergesort

Slide 20: Bottom-up mergesort

Exam angle

PredictionQ1

Merge sort [RUH, AMM, DMM, JED, KWI, DXB, SFO]. (Quiz 2)

Compare with the model answer

Split to single items, then merge: [AMM, RUH] [DMM, JED] [DXB, KWI] [SFO] → [AMM, DMM, JED, RUH] [DXB, KWI, SFO] → [AMM, DMM, DXB, JED, KWI, RUH, SFO].

Slide 21 / 40

Bottom-up mergesort: Java implementation

Slide 21: Bottom-up mergesort: Java implementation
Slide 22 / 40

Mergesort: visualizations

Slide 22: Mergesort: visualizations
Slide 23 / 40

Sort countries by gold medals

Slide 23: Sort countries by gold medals
Slide 24 / 40

Sort countries by total medals

Slide 24: Sort countries by total medals
Slide 25 / 40

Sort music library by artist

Slide 25: Sort music library by artist
Slide 26 / 40

Sort music library by song name

Slide 26: Sort music library by song name
Slide 27 / 40

Comparable interface: review

Slide 27: Comparable interface: review
Slide 28 / 40

Comparator interface

Slide 28: Comparator interface
Slide 29 / 40

Comparator interface: system sort

Slide 29: Comparator interface: system sort
Slide 30 / 40

Comparator interface: using with our sorting libraries

Slide 30: Comparator interface: using with our sorting libraries
Slide 31 / 40

Comparator interface: implementing

Slide 31: Comparator interface: implementing
Slide 32 / 40

Comparator interface: implementing

Slide 32: Comparator interface: implementing
Slide 33 / 40

Slide 33

Slide 33: Slide 33
Slide 34 / 40

Stability

Slide 34: Stability

Notes

  1. Stable sort: equal keys keep their relative order. Insertion and merge sort are stable; selection sort (and quicksort) are not.

Exam angle

PredictionQ1

Which sort is stable?

Slide 35 / 40

Stability

Slide 35: Stability
Slide 36 / 40

Stability: insertion sort

Slide 36: Stability: insertion sort
Slide 37 / 40

Stability: selection sort

Slide 37: Stability: selection sort
Slide 38 / 40

Stability: mergesort

Slide 38: Stability: mergesort
Slide 39 / 40

Stability: mergesort

Slide 39: Stability: mergesort
Slide 40 / 40

Sorting summary

Slide 40: Sorting summary