Mergesort : Revision

Question

Does merge sort work by;

taking a list of values

splitting it in to two

take the first element of each list, the lowest value one goes in to a new list(and i guess removed from the original). comare the next two numbers - do this until one list is empty, then place the rest of the other list at the end ofthe nw list?

Also, what are the ramifications of doing this on a linked list?

Thanks

Answer 1

What you described is only merging (without sorting), sorting is done recursivly in merge sort.

Also, what are the ramifications of doing this on a linked list?

It's probalby too expensive to split linked lists, if you have two sorted lists you could easily merge them maintaining the order.

Answer 2

A merge sort works by splitting an array in two then calling merge sort on each half. When merge sort is called with only one element it simply returns it. The merging takes place after the recursion and puts the array back together in sorted order.

array mergesort(array)
{
    if(array.len == 1) return array;

    array temp1 = mergesort(array.firsthalf);
    array temp2 = mergesort(array.secondhalf);

    return merge(temp1, temp2);
}

The problem with applying merge sort to a linked list is you have no easy way of splitting it in half. You'd have to iterate along until you got to half way. This consumes extra time and will unduly affect the performance of your merge sort. With an array you can do simple constant time integer operations to divide it in two.