1. | Most sorting algorithms are __________-based. |
| |

2. | Merge sort and quicksort are ______ ___ ______ algorithms. |
| |

3. | Average performance for tree sort, merge sort, quicksort and heapsort. |
| |

4. | Average performance for bubble sort, selection sort, and insertion sort. |
| |

5. | The output from a sort algorithm is one ___________, or re-ordering, of the input. |
| |

6. | In the quicksort algorithm, the element used to divide the list is called the _____ value. |
| |

7. | A humorous sorting algorithm which randomly permutes the list and checks to see if it’s sorted. |
| |

8. | When a sorting algorithm keeps elements with the same value in the same order they appear in the original list, it is said to be ______. |
| |

9. | A sorting algorithm that divides the list into two sublists: elements lower than a specific value and elements higher than a specific value. |
| |

10. | Type of sorting algorithm where data is distributed from input to multiple intermediate structures which are then gathered in order and output. |
| |

11. | A sorting algorithm that builds a heap out of the data, then repeatedly removes the largest element from the heap and inserts it into the sorted list. |
| |

12. | A sorting algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. |
| |

13. | A simple sorting algorithm that works by repeatedly stepping through a list, comparing each pair of adjacent items and swapping them if they are in the wrong order. |
| |

14. | In the quicksort algorithm, the _________ operation reorders the list so that the elements are ordered into low values and high values compared to a specific value. |
| |

15. | A sorting algorithm that repeatedly divides a list until each element is a separate list. It then combines and sorts adjacent lists until the whole list is fully sorted. |
| |

16. | A sorting algorithm which operates by counting the number of objects that have each distinct key value, then determining the positions of each key value based on the counts. |
| |

17. | A sorting algorithm that builds the final sorted array one item at a time by removing an item, finding the location it belongs within the sorted list, and inserting it there. |
| |

18. | A situation where memory use can be reduced at the cost of a slower program (and, conversely, the computation time can be reduced at the cost of increased memory use) is called: |
| |

19. | A distribution sort which works by separating a list into a number of containers which are sorted individually. The containers are visited in order and the elements are put back into the array. |
| |

20. | A sorting algorithm that sorts a list into an unsorted sublist and a sorted sublist. It repeatedly finds the smallest element in the unsorted sublist and swaps it with the leftmost unsorted element. |
| |