Two Algorithms

Based on these insights, we can create the skeleton of two distinct algorithms.

• Break the list into two lists of size n/2. Sort each separately. Now, put the two sorted lists together in linear time.
• In linear time, split the list into two lists such that all the small elements are in one list and all the big elements are in the other. Once the two sublists are sorted recursively, the final result is sorted.

Recognize these algorithms?