Detour: Divide-and-Conquer Algorithms
Explore the principles of divide-and-conquer algorithms through the example of sorting lists. Understand how the Merge algorithm combines sorted lists and how MergeSort recursively sorts unsorted lists efficiently with O(n log n) runtime. Gain insight into applying these computational techniques to biological data analysis.
We'll cover the following...
We'll cover the following...
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 and into a single sorted list (figure below). The Merge algorithm combines two sorted lists into a single sorted list in ...