Detour: Divide-and-Conquer Algorithms

We’ll use the problem of sorting a list of integers as an example of a divide-and-conquer algorithm. We begin from the problem of merging, in which we want to combine two sorted lists $List_{1}$ and $List_{2}$ into a single sorted list (figure below). The Merge algorithm combines two sorted lists into a single sorted list in $O(|List_{1}| + |List_{2}|)$ time by iteratively choosing the smallest remaining element in $List_{1}$ and $List_{2}$ and moving it to the growing sorted list.