Sorting

Not a very popular topic in interview. It is nonetheless the fundamental of algorithms that will help you understand and solve other problems.

Question

Given an array of size n, return an array that is sorted. Can you do it in place?

Analysis

Can't believe to get back this topic again. Many algorithm courses use sorting as an introduction to algorithm design paradigms and techniques to analyze time and space complexity. Here we'll try to imitate the same approach.

Solutions

We will go over two iterative approaches first - bubble sort and insertion sort. Then we will look at two solutions using the divide and conquer paradigm. Lastly, we will discuss how to sort efficiently with the help from data structure.