Sorting

Insertion sort usually runs faster than merge sort for small input sizes; once the input size n becomes large enough, merge sort’s advantage of log n versus n compensates for the difference in constant factors [CLRS, p. 12].

You need to know how to sort. You should know the details of at least one n log (n) sorting algorithm. You must know merge sort and quick sort. Don’t use bubble-sort.

---

Table of contents

• Heap Sort
• Insertion Sort
• Merge Sort
• Quicksort
• Selection Sort