There are lots of reasons for choosing one sorting algorithm over another. We might choose an algorithm because it is simple, fast, uses less memory, or works well on the kind of data we have. An algorithm that is easier to understand is also easier to write and debug. However, often the simplest sorts are not efficient. Efficiency is usually the first thing we look for.

We can compare algorithms in terms of time and space efficiency.

Space efficiency refers to the amount of space that an algorithm uses. An algorithm that uses less space and runs faster is more efficient.

• We measure efficiency by the size of the input. For a sorting algorithm the input is the array of elements to be sorted, so the size of the input is the number of elements. We will use n for the number of elements being sorted.
• We can measure the time efficiency of an algorithm by counting how many statements get executed when the algorithm runs.

We are most interested in how the running time grows as the size of the input grows, so we can ignore statements that get executed the same number of times each time the algorithm is run.

• Instead we look at those statements that get executed a different number of times depending on the size of the input.
• In sorting algorithms, the common operation is a comparison, so we usually count comparisons when we consider sorting algorithms.
• As the number of elements to be sorted grows, the number of comparisons required grows as well.

We want to find the relationship between the two growth rates.

The selection sort has an outer loop that runs n-1 times, where n is the size of the input array.

The inner loop runs a variable number of times, ranging from 1 to n-1, depending on the index of the outer loop.

So, we can say that the time efficiency of the selection sort algorithm is on the order of n^2.

• We use big-oh notation saying that selection sort is O(n^2). This means that the running time of the selection sort algorithm will be no worse than on the order of n^2 units of time, where n is the size of the input.
• We are not interested in how long a unit of time is because we use big-oh notation only to compare algorithms to each other; we are not trying to find out how long the algorithm takes to run.
• Note that because O(n^2) is an efficiency no worse than n^2, we could also say that selection sort is O(n^3) or O(n^4 ) or O(2n). However, we want to get as close as possible to an algorithm’s real time efficiency.
• We can analyze insertion sort in almost the same way.
• Its two nested loops run n times each, so the statements (comparisons) inside get executed approximately n^2 times.
• The insertion sort algorithm is therefore also O(n^2).
• An algorithm,  that  was  O(n) would be more efficient than one that is O(n^2 ).
• Likewise, O(n^3 ) and O(2n) algorithms are less efficient than O(n2 ).

Table below shows various efficiency values for algorithms ranked from most efficient to least efficient. Note that for small values of n there is not much difference, but when n gets large, the efficiency of an algorithm makes a big difference.

The insertion sort has O(n^2) in the worse case. However, in an verage when the data is random, it is a more efficient sort.

These two sorts can also be implemented to work on objects.