In this chapter, the input for any algorithm is a vector of elements (key values) unless stated otherwise. These elements can be of any type: numeric, character, logical, or complex.
Consider an input vector V of elements i1,i2,...,in . These elements are said to be sorted provided their corresponding values satisfy a particular order. In other words, the elements of vector V are said to be sorted in non-decreasing order provided their values satisfy the condition i1<i2<,...,<in .
All the algorithms presented in this chapter can handle the special case of sorting, that is, duplicate elements in a given input vector; however, only some of them perform it optimally. An algorithm is said to be performing optimally provided it retains the original position of duplicate elements without redundantly ordering them, thereby reducing computation time.
The simplest way to compare performances of two algorithms is by assessing their computational system runtime...