Investigation: Sort Wars If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many different sorting algorithms? Your task is to investigate these and other questions in relation to the algorithms selection sort, insertion sort, merge sort, and quicksort

Task

1. Explain the selection sort, insertion sort (fast or slow), merge sort, and quicksort algorithms in such a way that an intelligent lay person would be able to understand how they work. Whilst you may wish to consult the lecture notes to re-familiarise yourself with the inner workings of each algorithm, your explanations should not include any code (or pseudo code). However, you will likely need to use general concepts such as compare and swap, and you will almost certainly need to use procedural words such as if and repeat.

You may find it helpful to consider how you would explain the algorithms to your friend studying a non-IT degree. One approach would be to treat each algorithm as if it were a game for which you need to define the rules. For example, here is how you could describe the bubble sort algorithm as if it were a game of solitaire played with a deck of cards that contain the values to process

2. Write a set of guidelines for each algorithm to help someone decide which one would be most appropriate for a particular situation. Include in your guidelines a description of the advantages and disadvantages, together with an indication as to why those characteristics apply, and an explanation of the running cost (in Big-O notation). Your goal is to provide enough information so that someone unfamiliar with the inner workings of each algorithm would be able to decide which one is right for them. For example, if someone was considering using counting sort to sort a collection of values then the following brief information could help them decide if it was appropriate or not.

Algorithm Counting Sort

Description Count the number of times each different value appears, then overwrite the values in lowest-to-highest order, with each value repeated according to the counts

Advantages Usually faster than any of the comparison-based sorts. Algorithmic complexity is O(n + k), irrespective of the data order, where n is the list length and k is the number of distinct values that might occur. Typical case is where k is much less than n, in which case the cost is O(n).

Simple to code

Disadvantages Only usable where the values to be sorted can be used to index an array of value counts, which usually means the values are integers over a small range. In other words, the algorithm cannot be used to sort common non-integral values such as strings and floats, and it is inappropriate even for integers if the range of values is large.

Requires an auxiliary array (to store the counts) of size equal to the number of different possible sort values. If the range of values is large, the cost of allocating and maintaining this array could be significant.

When to use If your circumstances allow, it is hard to beat this algorithm, but because it places very tight restrictions on the nature of the data to sort, you will often have to choose another approach.