AP Computer Science A · Lesson 4.20 · Unit 4 · CED topic 4.17

Merge sort

Name:   Date:  

1 Why this lesson matters

Read the opening paragraph and the "Required content" box on the lesson page. In your own words, explain each objective below.

17.A. Determine the result of executing recursive algorithms that use strings or collections.

17.B. Determine the result of each iteration of a binary search algorithm used to search for information in a collection.

17.C. Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

2 The idea

Read this section. In your own words, summarize the main idea.

3 The merge step

Read this section. In your own words, summarize the main idea.

4 The code

Read this section. In your own words, summarize the main idea.

5 Tracing the divide and merge

Read this section. In your own words, summarize the main idea.

6 How much faster?

Read this section. In your own words, summarize the main idea.

7 Worked example

Read the "Worked example" box. Then, without looking back, try writing your own answer below.

How many times can an array of 16 elements be halved before the pieces have 1 element?

8 Exam focus: avoid this mistake

Read the "Exam focus" box, then restate it in your own words.

9 Sum it up

In two or three sentences, explain this lesson's main idea to someone who has not read it.