Sorting is the process of arranging items systematically, into different groups or order. The main purpose of sorting information is to make it easier to deal with the items or search for information.
Examples of why humans might like to sort items include:
Computer programs also need to sort data so that they can locate information and then perform operations on this information.
For our purposes we will be humans pretending to act like computers!
It can be easy to sort items when there are only a small number of items, but it becomes much more difficult when there are many items to sort. We can use algorithms to make the sorting process more efficient. There are many sorting algorithms, we will look at the following 5 algorithms:
Selection Sort involves systematically finding the numbers in order and swapping them into position until the numbers are in order.
The following steps and example show how to sort a list into ascending order (smallest to biggest) using the selection sort algorithm.
Step 1 
Scan the list of numbers to find the smallest number and swap this number with the first number in the list 

Step 2 
Scan the list of numbers to find the second smallest number and swap this number with the second number in the list 

Step 3 
Scan the list of numbers to find the third smallest number and swap this number with the third number in the list (in this case the number is in correct position) 

Step 4 
Scan the list of numbers to find the fourth smallest number and swap this number with the fourth number in the list 


The list is now sorted in ascending order 

Insertion Sort involves moving from left to right and determining the correct position for each number and inserting into their correct position
The following steps and example show how to sort a list into ascending order (smallest to biggest) using the insertion sort algorithm
Step 1  Compare the second number with the first number and if it’s less than the first number insert it before the first number  
Step 2  Compare the third number with the first two numbers and insert the number in the correct position so that the first 3 numbers are in ascending order 


Step 3  Compare the fourth number with the first three numbers and insert the number in the correct position so that the first 4 numbers are in ascending order  
Step 4  Compare the fifth number with the first four numbers and insert the number in the correct position so that the first 4 numbers are in ascending order  
The list is now sorted in ascending order 

Bubble sort involves comparing pairs of adjacent elements of the sequence, if they are in the wrong order swap them and do this until there are no swaps to do.
The following steps and example show how to sort a list into ascending order (smallest to biggest) using the bubble sort algorithm
Step 1  Compare the first 2 numbers and swap them if they are out of order.  
Step 2  Compare the next 2 numbers and swap them if they are out of order  
Step 3  Compare the next 2 numbers and swap them if they are out of order  
Step 4  Compare the next 2 numbers and swap them if they are out of order  
The largest number has now “bubbled” to the end of the list. Now repeat this process starting at the start again. 


Step 5  Compare the first 2 numbers and swap them if they are out of order. 


Step 6  Compare the first 2 numbers and swap them if they are out of order.  
Step 7  Compare the first 2 numbers and swap them if they are out of order. 


The second largest number has now “bubbled” to the second last position of the list. The last 2 numbers do not need to be compared as they are in the correct position. Now repeat the process starting at the start again. 


Step 8  Compare the first 2 numbers and swap them if they are out of order.  
Step 9  Compare the first 2 numbers and swap them if they are out of order. 


The third largest number has now “bubbled” to the third last position of the list. The last 3 numbers do not need to be compared as they are in the correct position. Now repeat the process starting at the start again. 


Step 10  Compare the first 2 numbers and swap them if they are out of order. 


The fourth largest number has now “bubbled” to the fourth last position of the list. Therefore the smallest number will also be in the correct position. The list has now been sorted into ascending order. 

The bucket sort algorithm involves placing data in buckets or bins. These bins may represent single numbers or they may represent ranges of numbers that then have to be sorted using another sorting algorithm ( eg. insertion)
The following steps and example show how to sort a list into ascending order (smallest to biggest) using the bucket sort algorithm
The set of data to be sorted is
2  4  3  7  9  3  7  4  3 

Step 1: The data consists of single digit numbers so we would usually sort them into single range bins 09. Move from left to right along the data set and place (or point) each data element into the correct bin
0  1  2  3  4  5  6  7  8  9 

2  3  4  7  9  
3  4  7  
3 
Step 2: Remove empty bins and list numbers in order from each bin
2  3  3  3  4  4  7  7  9 

Example: Use the bucket sort algorithm to manually sort the following set of data
12  34  33  75  39  23  74  34  38 

Step 1: Data is 2 digit numbers so would usually sort into bins representing the tens digit. Move from left to right along data set and place/ point each data element into correct bin
0  1  2  3  4  5  6  7  8  9 

12  23  34  75  
33  74  
39  
34  
38 
Step 2: Use the insertion sort algorithm to sort elements in bins that have multiple elements
a) Sorting the 3's column
0  1  2  3  4  5  6  7  8  9 

12  23  33  75  
34  74  
39  
34  
38 
0  1  2  3  4  5  6  7  8  9 

12  23  33  75  
34  74  
39  
34  
38 
0  1  2  3  4  5  6  7  8  9 

12  23  33  75  
34  74  
34  
39  
38 
0  1  2  3  4  5  6  7  8  9 

12  23  33  
34  
34  
38  
39 
b) Sorting the 7's column
0  1  2  3  4  5  6  7  8  9 

12  23  33  74  
34  75  
34  
38  
39 
Step 3: Remove empty bins and list numbers in order from each bin
12  23  33  34  34  38  39  74  75 

The merge sort algorthm divides the list of numbers into smaller and smaller groups, orders them then combines them back together.
Example: Use the merge sort algorithm to manually sort the following set of data
23  53  4  34  76  45  23  14 

Step 1: Divide the list into two lists of equal size (or nearly equal if there are an odd number of items).
23  53  4  34  76  45  23  14 

Step 2: Continue to divide the lists until they are the smallest unit (1 element)
23  53  4  34  76  45  23  14 

23  53  4  34  76  45  23  14 

Step 3: Compare each element with the adjacent list and merge together sorted in order
23  53  4  34  45  76  14  23 

Step 4: Continue to merge adjacent lists by comparing the first numbers of each list and listing the numbers in order
4  23  34  53  14  23  45  76 

4  14  23  23  34  45  53  76 

We want to use the insertion sort algorithm to manually sort the following set of data and then find the median.
$72,26,63,48,31,55,17$72,26,63,48,31,55,17
Use the insertion sort algorithm to arrange these numbers in ascending order.
Write one step of the insertion sort at a time, separating the numbers in the step with commas.
Hence find the median of the data set.
We want to use the bucket sort algorithm to manually sort the following set of data and then find the median.
$81,31,12,94,65,28,47,54,76,93,71,11,35,27,85,42,66,56$81,31,12,94,65,28,47,54,76,93,71,11,35,27,85,42,66,56
Sort the numbers into the buckets below based on their tens digit.
When entering numbers in a column, each number belonging to that column should be entered in the order that they appear in the list. For example, if $12$12 appears before $11$11 in the list, then $12$12 should be before $11$11 in the column.
Bucket  $1$1  $2$2  $3$3  $4$4  $5$5  $6$6  $7$7  $8$8  $9$9 
$\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  
$\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$ 
Sort the numbers in each bucket in ascending order from top to bottom.
Bucket  $1$1  $2$2  $3$3  $4$4  $5$5  $6$6  $7$7  $8$8  $9$9 
$\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  
$\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$  $\editable{}$ 
Arrange the data set in ascending order.
$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$,$\editable{}$
Hence find the median of the data set.