Merge Sort

Sorting algorithms, they are cool, We've already learned one simple rule. Now we have a new contender, This thing is called "merge sort" (the mender). First, you split the array in half, Do the same for the other halves. Repeat until you find yourself, With lengths of one, no more splits left. Merge each half by doing these steps: Have two pointers: a and b, "A and b?" you ask; you'll see. a is the first element of the first half, b is the first of the second half. Find which element is smaller, If a is smaller, don't growl or holler: Put it in something, Called an "auxiliary listing." Auxiliary lists are extra lists, They affect space complexities. Now what you need to do, Is move element a to the list anew. Move a to the right, now time for b: If b's smaller, you'll agree, Do the same as with element a, Put it in the auxiliary array. Move b to the right, repeat the stride, When one ends, the rest slides inside. After that, copy the auxiliary list, Back to the main list; don't resist. Repeat until all halves are done, What you've seen is sorting fun. The list is sorted, now you're free, Next time we'll learn more algorithms, you'll see.