Round 2: Sorting

Sorting is an ubiquitous task: we can order lists of students by their student id number, web access logs by host, etc. Sorting is also used as a prerequisite or subroutine in many other algorithms:

  • ​ binary search,

  • ​ graph search algorithms,

  • ​ and so on.

With proper algorithms, sorting can be done very efficiently.

In this round we will introduce few of the most common and important sorting algorithms. In addition to these, several others exist — this wikipedia page contains many others and also a comparison of several algorithms with respect to the required running time, extra space etc.

In addition to the algorithms, we’ll also familiarize ourselves with the “divide and conquer” algorithm design paradigm.

Contents:

Material in Introduction to Algorithms (Aalto access):

  • ​ Insertion sort: Sections 2.1 and 2.2

  • ​ Mergesort: Section 2.3

  • ​ Quicksort: Chapter 7

  • ​ Lower bounds for sorting: Section 8.1

  • ​ Sorting in linear time: Section 8.2–8.4

Other sources:

Some external links: