Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Discussion on Sorting Algorithms

Explore essential sorting algorithms used in computer science such as merge-sort, quicksort, and heapsort. Understand their advantages, in-place and randomized behaviors, and how counting and radix sorts handle different data types efficiently.

We'll cover the following...

Additional notes

Sorting is the fundamental algorithmic problem in computer science, and it has a long history. KnuthD. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, second edition, 1997. attributes the merge-sort algorithm to von Neumann (1945). Quicksort is due to HoareC. A. R. Hoare. Algorithm 64: Quicksort. Communications of the ACM, 4(7):321, 1961.. The original heapsort algorithm is due to WilliamsJ. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347–348, 1964., but the version presented here (in which the heap is constructed bottom-up in O(n)O(n) time) is due to FloydR. W. Floyd. Algorithm 245: Treesort 3. Communications of the ACM, 7(12):701, 1964.. Lower-bounds for comparison-based sorting appear to ...