Syllabus
Sequential algorithms for internal sorting. Algorithms based on comparisons, bucket sorting, estimates of their complexity. A survey on well-known sorting algorithms (Bubblesort, Insertionsort, Quicksort, Mergesort,...) and their modifications. Some little-known sorting algorithms.
Parallel sorting. Parallel models of computation, measures of complexity of parallel algorithms. Special parallel architectures for sorting (sorting networks). Sorting on multi-purpose parallel machines with various types of processor interconnection ( linear, tree, ...), shared memory computers. Synchronous and asynchronous sorting.
Sorting of external files on tapes and discs. Complexity measures for external sorting.
Annotation
A survey on sorting algorithms and their analysis. Sequential and parallel sorting algorithms, internal and external sorting.