Heapsort is really a beautiful algo. When I first wrote my heap implementation for a data structures class, our prof didn't mention it until well after we had finished. At that point she was like "So, now if you dump everything out of your heap, do you notice anything about the data?" I do love it.
Mergesort always irked me for some reason. Maybe it's the recursion. I just always leaned more towards quicksort. Usually when I have to sort something I end up using quicksort rather than mergesort if the language doesn't have a built in sort function.