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)
Let's say you're merging the ordered sequences {1, 3, 5, 10, 12} and {2, 4, 7, 8, 9, 11, 15}. Just figure out by yourself the most efficient way of merging them into a single ordered sequence (it should be O(n)) and ihbt :(
You honestly haven't. I have an exam in this shit tomorrow ("Algorithms and Data Structures in C++") and one of the questions I can draw is Insertion and Mergesort. I get why Insertionsort is O(n^2) intuitively, but mergesort trips me the fuck up.
Name:
Anonymous2011-01-16 22:33
Continuing post# 4: I can also draw "Sequential and Binary Search" which sort of have the same relationship to each other as Merge does to Insert (it looks like) but while I get how Binary is O(log n) I don't get why Mergesort is.
Name:
Anonymous2011-01-16 22:38
say you are looking at two lists. point to the first element of both lists. start going down one of the lists comparing each element to the wherever the pointer in the second list is. lets say we're doing ascending order. if the element in the first list is less than the second, put it in a new list. move the first pointer to the next element in the first list. repeat until the element in the second list is greater than the first.
when that happens put that element in the new list and move that pointer up to the next element in the second list. repeat until you get to the end of one of the lists. when that happens you can just empty the remaining elements into the new list because everything else had to have been less than those.
Name:
Anonymous2011-01-16 22:39
AAAAand Wikipedia's got my back again
"Merge sort incorporates two main ideas to improve its runtime:
1. A small list will take fewer steps to sort than a large list.
2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted (see the merge function below for an example implementation)."
Thanks, appreciate it. That, along with Wikipedia's article sorted it out for me.
My main sticking point was along the lines of "Once everything has been split up, isn't it pretty much just Insertion Sort that puts it back together?" but I hadn't considered that Insertion Sort is efficient as fuck if it works on an already-sorted list which is what the initial split-up sort-of does.
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.