AP® Computer Science A glossary
Merge sort
Course: AP® Computer Science A Shows up in: Unit 4: Data Collections
A recursive sort that divides an array into one-element subarrays, then merges sorted subarrays back together in order.
Appears in the course and exam description (CED): 4.17.C.14.17.C.2
Merge sort splits the array in half again and again until each subarray has one element. It then merges pairs of sorted subarrays by repeatedly taking the smaller front element, until one sorted array remains. The left half is sorted completely before the right half.
Example
// {38, 16, 27, 5}
// divide: {38, 16} {27, 5} then {38} {16} {27} {5}
// merge: {16, 38} {5, 27} then {5, 16, 27, 38}