For some problems, it is not obvious how to do anything other than comparisons. It's easier to design and analyze algorithms without having to think about unnecessary problem-specific details Some comparison sorting algorithms work quite well, so there is not so much need to do something else. There are dozens of sorting algorithms. Baase covers around seven. Merge sort and quick sort are different examples of divide and conquer, a very general algorithm design technique in which one partitions an input into parts, solves the parts recursively, then recombines the subproblem solutions into one overall solution.
Quick sort is an example of randomization and average case analysis.
If we have a comparison sorting algorithm, we can't really say how many machine instructions it will take, because it will vary depending on how complicated the comparisons are. Since the comparisons usually end up dominating the overall time bound, we'll measure time in terms of the number of comparisons made. So even if you're sorting small lists it pays to use a good algorithm such as quicksort instead of a poor one like bubblesort. You don't even have the excuse that bubblesort is easier, since to get a decent sorting algorithm in a program you merely have to call qsort . Lower bounds A lower bound is a mathematical argument saying you can't hope to go faster than a certain amount.