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)

WOOOOOOOOOOO

I passed with flying fucking colors. Didn't get a single question about Mergesorts (I drew the question on Hash Tables) but who gives a fuck, I was excellent. There was *one* question the teacher asked that I couldn't answer, otherwise it was 20 minutes of pure own zone.