Sorting Secret - Computerphile

Two different sorting algorithms are actually the same. Professor Graham Hutton explains.

Note from Professor Hutton: It's great to see all the discussions here! To clarify a point raised in some of the comments, the video shows that if you consider the essential underlying idea of selection sort and insertion sort, in terms of how they decompose the problem of sorting, then they perform the same operations but in different orders. Using the picture in the video, selection sort proceeds column at a time and insertion sort proceeds row at a time, but they both perform the same 'triangle' of operations in the end. A particular implementation of these sorting methods may optimise the process in some way, e.g. in a sequential implementation each row can stop comparing numbers once the point of insertion is found. But this is an implementation detail that is dependent on the computational model used, such as sequential versus parallel, or imperative versus functional, rather than part of the essential means by which the sorting methods work.

Slow Loris Attack: https://youtu.be/XiFkyR35v2Y
Cracking Windows by Atom Bombing: https://youtu.be/rRxuh9fp7QI
Quantum Computing: https://youtu.be/BYx04e35Xso
Babbage's Analytical Engine: https://youtu.be/5rtKoKFGFSM
Quicksort: https://youtu.be/XE4VP_8Y0BU
Getting Sorted: https://youtu.be/kgBjXUE_Nwc

http://www.facebook.com/computerphile
https://twitter.com/computer_phile

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com