Which of the following sorting algorithms has a worst case complexity of \Theta(n \log n)?

Mergesort
  • Bubble Sort
  • Radix Sort
  • Selection Sort
  • Insertion Sort

Bubble Sort, Insertion Sort, and Selection Sort are referred to as "quadratic sorts" because of their worst-case time cost.

The cost of Radix Sort depends both on the number of records and the number of digits in the key.