Merge Sort

Introduction

Welcome all! This is just a quick explanation of the merge sort algorithm, I recently saw it and realised I hadn't heard of it before, I guessed there would be a few like me.

Merge Sort

So...you've never heard of it? (Or you have and think I'm just a retard.)

This is what we do, we take a list of say n numbers, and split them in into two equal sized piles (lists of numbers), how do we sort those? we merge sort them, yes it's defined in terms of itself, so it's recursive, note that I haven't fully defined the algorithm yet.

Ok, I'll explain, obviously when we have only 1 number in a pile we don't need to sort it. So we merge it with the other corresponding pile we got from splitting the pile before this. Ok that's a bad explaination, here's a diagram, of sorting the word "test" (in alphabetical order)

		    original pile :   "test"
				/     \
	       two sub-piles : "te"   "st"
			       /  \    /  \
	    four sub-piles:  't'  'e' 's'  't'

	    merge four sub-piles: "et" and "st" are resultant two sub-piles
	    merge two sub-piles: "estt" is resultant pile.

So that's sorted out. ;) (Damn I'm funny.)

One thing we haven't dealt with is how do you merge the sub-piles?

It's easy - we compare the two highest order elements, and put the higher in a new array, then we compare the next element of the array which the higher element belonged to, to the element which was lower than the highest element in the other array, and continue on like this.

That was probably worse than my first explaination, here's another one:

Merging four sub-piles: 't' 'e' and 's' 't'
First we merge 't' and 'e', to get "te" (just one compare)
Then we merge 's' and 't', to get "st" (just one compare)
Then we merge "te" and "st"

First we compare 't' and 'e' and put 't' in the destination array.

Then we compare 's' and 'e' and put 's' in the destination array.
We are left with only two sorted elements so we put them in the dest. array.

Finally, if we have to split a pile of an odd number of elements, into two we just give one pile one more element than the other.

I'm sure you can see that this is easily done with code recursion, if you're not familiar with code recursion you can read my article on it, in this issue.

That's it. I hope you understand.

Merge sort is closely related to quick sort (the fastest sorting algorithm, in general).

Conclusion

Well, I hope you liked this article, it's sloppy because I really couldn't be bothered checking it at all because... :|

p/v