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:    • Slow Loris Attack - Computerphile  
Cracking Windows by Atom Bombing:    • Cracking Windows by Atom Bombing - Co...  
Quantum Computing:    • Quantum Computing 'Magic' - Computerp...  
Babbage's Analytical Engine:    • Babbage's Analytical Engine - Compute...  
Quicksort:    • Quick Sort - Computerphile  
Getting Sorted:    • Getting Sorted & Big O Notation - Com...  

  / computerphile  
  / 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