I don't get Mergesort

Seriously.

I can understand the general principle, i.e. Split up list into smaller bits (until they're only one element long) then merge back in correct order, but how is the merging performed? It looks, from the code examples that I'm looking at, that the merging should be in-efficient as all fuck. Can somebody tell me why it isn't?

(Any explanation you'd care to offer can assume array or linked list, either works for me)

>>13
i dont get hashtables, how do they work?

the way i picture them is you create a huuuge array and then add/find all elements using hash(key).... but then how do you deal with space issues?