Insertion sort has one desirable property: Its performance is O(n) if the array is
already sortedȌsee Exercise R14.13. This is a useful property in practical
applications, in which data sets are often partially sorted.
A DVANCED T OPIC 14.2: Oh, Omega, and Theta
We have used the big-Oh notation somewhat casually in this chapter, to describe
the growth behavior of a function. Strictly speaking, f(n)=O(g(n)) means that f
grows no faster than g. But it is permissible for f to grow much slower. Thus, it is
technically correct to state that f(n)=n 2 +5nɨ3 is O(n 3 ) or even O(n 10 ).
Computer scientists have invented additional notation to describe the growth
behavior of functions more accurately. The expression
means that f grows at least as fast as g, or, formally, that for all n larger than some
threshold, the ratio f(n)/g(n) ʏ C for some constant value C. (The Ɗ symbol is the
capital Greek letter omega.) For example, f(n)=n 2 +5nɨ3 is Ɗ(n 2 ) or even Ɗ(n).
means that f and g grow at the same rateȌthat is, both f(n)=O(g(n)) and
f(n)=Ɗ(g(n)) hold. (The ź symbol is the capital Greek letter theta.)
The ź notation gives the most precise description of growth behavior. For
example, f(n)=n 2 +5nɨ3 is ź(n 2 ) but not ź(n) or ź(n 3 ).
The Ɗ and ź notation is very important for the precise analysis of algorithms.
However, in casual conversation it is common to stick with big-Oh, while still
giving as good an estimate as one can.
14.4 Merge Sort
In this section, you will learn about the merge sort algorithm, a much more efficient
algorithm than selection sort. The basic idea behind merge sort is very simple.