Let's begin our analysis by determining which sort was the most space-efficient. We discussed in our previous lesson that space efficiency can be measured by calculating the number of memory cells a particular sort requires. For simplicity, we will assume that a memory cell can hold one number. This means that a sort with five numbers would require at least five memory cells just to store the numbers in the computer. The total number of memory cells needed for sorting will depend on how many additional cells the algorithm requires to order the numbers.
Type of Efficiency Measure
Space Amount of computer memory
For each sort, calculate the number of memory cells that the algorithm required, and then enter your answers in the boxes below to see if they are correct. You can return to the pages on sorting by clicking the name of the sort. The pages will open in a new browser window. Do not forget to consider the memory requirements of the swap operation in your calculations.
Of the three sorts, we see that the Insertion Sort and the Selection Sort were the most space-efficient. These sorts order the items within the list using the swap operation rather than copying items to a new list. Since the Simple Sort copies every item to a new list, it requires twice as much computer memory. Remember, however, that the swap operation requires a temporary memory cell. That is why your answers for the Selection Sort and Insertion Sort may have been a little surprising.