thank you BrowserUk your replies are all very helpful for me, especially about testing the input parameter. Only a little disappointment... regarding the number of comparisons i believe that your code doesn't agree with my way of counting comparisons only why it counts also the comparisons in the while condition, the number 3(n/2) refers to comparisons among elements of the input list.