Subject: Sorting (3 cr)

A popular way to optimize sorting algorithms such as Mergesort and Quicksort is to switch to a lighter sorting algorithm at a certain point. The purpose of this assignment is to test the performance of some optimized sorting algorithms. The task is to find out at what point one should switch from the complex sorting algorithm to the simpler one.

Algorithms to optimize:

• Mergesort
• Quicksort
• Radixsort:
  • MSD radixsort
  • LSD radixsort
  • Adaptive radixsort
  • Forward radixsort

Some references

General literature about algorithms

• Aho, Hopcroft, Ullman, Data Structures and Algorithms
• Aho, Hopcorft, Ullman, The Design and Analysis of Computer Algorithms
• Cormen, Leiserson, Rivest:  Introduction to algorithms
• Horowitz, Sahni:  Fundamentals of Data Structures in Pascal
• Kingston, Algorithms and Data Structures
• Knuth: The Art of Computer Programming, volume 3 / Sorting and Searching
• Sedgewick:  Algorithms / Algorithms in C / Algorithms in C++
• Weiss:  Data Structures and Algorithm Analysis (various versions for Pascal, C, C++ and Java)
• Wirth, Algorithms + Data Structures = Programs

Other references:

• Stefan Nilsson's papers