Tino APCS

Lesson A18

Next: A Non-recursive...

Merge and MergeSort

Lesson Overview: In Lesson A17, Quadratic Sorting Algorithms, we saw how the number of steps required increased N^2 when sorting N elements. In this lesson, we will study a recursive sort, called mergeSort that works by dividing lists in half. After solving a preliminary merge problem, you will code a recursive mergeSort.

A
A Non-recursive Mergesort
B
A Merge Algorithm
C
Recursive Mergesort
D
Order Of Recursive Mergesort
Y
Summary
Z-1
Lab 18.1 Merge
Z-2
Lab 18.2 Recursive Mergesort
Z-3
Lab 18.3 Final Sorting Investigation
Z-4
Sorting Practice Quiz
Lesson Vocab
MERGE

Taking two lists and putting them together.

MERGESORT

A sort that divides the list into two parts, sorts those parts, and then brings the sorted parts back together.