Now that you’ve seen a few (yes…just a few!) of the currently established sorting algorithms, we can start to discuss how they compare to each other. To compare which algorithm is better, we look at several characteristics including the speed, memory efficiency, and stability.
One common way to classify algorithms is using Big O Notation. (Follow the link to the Wikipedia article for more detailed information.) The factor that we care about in judging algorithm efficiency is how it reacts to different data sizes. As the number of elements in the unsorted list increases, what happens to the overall speed and efficiency? These questions are quite complex in nature, but they have already been researched and summarized nicely for the common sorting algorithms. This site has a wealth of nicely organized information for each of the algorithms you looked at in this chapter, in addition to several others that are a bit more complicated to implement.
Look at the pages for the four algorithms you worked with and try to answer the questions below, then check your answers.
2. Which of the algorithms are adaptive to different sets of data (how close they are to already being sorted)?