Chapter 1 of 6: Sorting algorithms
Traces merge sort's recursion tree and linear-time merge step to show why it runs in time.
Sorting algorithms are compared by worst-case running time in session 23 of MIT's Introduction to Computer Science and Programming using Python, taught by Ana Bell. Bell starts from binary search, which needs a sorted list and runs in , so sorting first pays off only across many queries. Bogo sort, with its unbounded worst case, comes next, followed by bubble sort and Knuth's remark on it in The Art of Computer Programming. Selection sort follows, and nested loops push both it and bubble sort to . Merge sort closes the session, splitting lists recursively and merging sorted halves in linear time to reach ; basic Python and Big Theta notation are assumed.
Sorting algorithms are compared by worst-case running time in session 23 of MIT's Introduction to Computer Science and Programming using Python, taught by Ana Bell. Bell starts from binary search, which needs a sorted list and runs in , so sorting first pays off only across many queries. Bogo sort, with its unbounded worst case, comes next, followed by bubble sort and Knuth's remark on it in The Art of Computer Programming. Selection sort follows, and nested loops push both it and bubble sort to . Merge sort closes the session, splitting lists recursively and merging sorted halves in linear time to reach ; basic Python and Big Theta notation are assumed.
The Art of Computer Programming
This lecture
Lecture 23 of 25 of Introduction to Computer Science and Programming using Python.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in