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

Discussion on Sorting Algorithms

Understand the history and principles behind major sorting algorithms such as merge-sort, quicksort, and heap-sort. Learn their advantages, limitations, and practical use cases including linked list sorting and integer sorting methods. Gain insights into the complexity and memory implications to select the appropriate sorting technique for different scenarios.

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 heap-sort 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 ...