When learning about sorting algorithms, I wanted to implement them to help me understand them better. This algorithm was originally invented by John von Neumann in 1948.
The Ruby script attached explains in real code what is going on. Play about with it.
Step by step:
- Pass through an array of unsorted numbers (i.e.
[4, 3, 2, 10]
) - Algorithm splits the array in half (left
= [4, 3]
and right= [2, 10]
) - Continue to split until only two numbers (we'll call this the
two_item_array
) - Find the lowest number in
two_item_array
(we'll call thissmallest
) - The
two_item_array
is sorted. Return it to parent. - Parent loops together all instances of
two_item_array
and compares the first number in all of them, and sorts them accordingly - Once looped, join all
two_item_array
items all together - All sorted!
The core purpose of the algorithm is split it until there is only two items. Once there is two items, you can compare the highest/lowest. There is now many instances of arrays with two items (which they are sorted). We begin to merge arrays based on the first number of every two item array (which are already sorted at this point). These blocks become four item arrays, eight item arrays, etc until the array is back to a complete array (except it is in order!).