People should learn bottom-up mergesort. It's not recursive, so it's easier to understand. Do multiple passes through the array, merging adjacent sub-lists:
First pass: merge every two neighboring single values into length-2 lists.
Second pass: merge every two neighboring length-2 lists into length-4 lists.
Third pass:merge every two neighboring length-4 lists into length-8 lists.
After log(n) passes, you're done!
This is probably what the magnetic tape drives were busy doing in those 1970s action movies, where the hero breaks into the computer room and fights the villains: they were driven by fortran programs, which didn't support recursion.
First pass: merge every two neighboring single values into length-2 lists.
Second pass: merge every two neighboring length-2 lists into length-4 lists.
Third pass:merge every two neighboring length-4 lists into length-8 lists.
After log(n) passes, you're done!
This is probably what the magnetic tape drives were busy doing in those 1970s action movies, where the hero breaks into the computer room and fights the villains: they were driven by fortran programs, which didn't support recursion.