What's the difference between quicksort and mergesort?

Question

Am I right in saying that in both algorithms, all you're doing is taking your structure, recursively splitting it into two, and then building up your structure in the right order?

So, what is the difference?

Edit : I have found the following algorithm for implementing the partition in quicksort, but I don't really understand how it works, , specifically the swop line that uses (hi + low) >>> 1 as an argument! Can anyone make sense of this?

private static int partition( int[] items, int lo, int hi ) 
{
    int destination = lo;
    swop( items, (hi + lo) >>> 1, hi );
    // The pivot is now stored in items[ hi ].
    for (int index = lo; index != hi; index ++) 
    {
        if (items[ hi ] >= items[ index ]) 
        {
            // Move current item to start.
            swop( items, destination, index );
            destination ++;
        }

        // items[ i ] <= items[ hi ] if lo <= i < destination.
        // items[ i ] > items[ hi ] if destination <= i <= index.
    }

    // items[ i ] <= items[ hi ] if lo <= i < destination.
    // items[ i ] > items[ hi ] if destination <= i < hi.
    swop( items, destination, hi );
    // items[ i ] <= items[ destination ] if lo <= i <= destination.
    // items[ i ] > items[ destination ] if destination < i <= hi.
    return destination;
}

Answer 1

Am I right in saying that in both algorithms, all you're doing is taking your structure, recursively splitting it into two, and then building up your structure in the right order?

Yes. The difference, however, is in when the structure is built in the right order. In Quicksort, the actual sorting step is done during the splitting (move elements to the left or right half, depending on the comparison with the pivot element) and there is no merging step to get back up the tree (as observed from the data point of view; your implementation may of course have stack unwinding), while in Mergesort, the sorting is done on the way up – the splitting step does not move elements at all, but on the way back up, you need to merge two sorted lists.

As for the performance comparisons: It is certainly true that the worst-case behavior of Quicksort is worse than that of Mergsesort, but the constant factor for the average case (which is observed almost exclusively in practice) is smaller, which makes Quicksort usually the winner for generic, unsorted input. Not that many people need to implement generic sorting routines themselves …