What's the difference between quicksort and mergesort?

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开发者_如何学C 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;
}

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 …

In worst case quicksort will have O(n^2) where mergesort will be O(n*log n)

Quicksort uses a pivot and sorts the two parts with the pivot as reference point with the risk that the pivot will be either maximum or minimum of the sorted array. If you will be choosing the wrong pivots you will end up with complexity n^2 (n^2 comparsions)

Mergesort as named is based on recursively dividing array into halfs of the same size and merging them back. Pretty nice explanations on wikipedia for example. Especially the picture with the tree-like brakedown seems to explain it pretty well.

Quicksort has a bad worst case, while Mergesort is always O(n log n) guaranteed, but typical Quicksort implementations are faster than Mergesort in practice.

Also, Mergesort requires additional storage, which is a problem in many cases (e.g. library routines). This is why Quicksort is almost always used by library routines.

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!

This is taking the average of hi and low, equivalent to (hi + low) / 2.

The implementation details of the underlying data-structures would also be a factor such as efficient random access (needed by quicksort) and the mutability of data-structures would have an effect on the memory requirements (particularly mergesort)

Yes, both Quicksort and Mergesort are divide-and-conquer algorithms.

Wikipedia's Quicksort page has a brief comparison:

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires O(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(log n) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

http://en.wikipedia.org/wiki/Sorting_algorithm there you have a quick overview of common sort algorithms. Quicksort and Mergesort are the first two ;)

For more information read through the information given on each of these algorithms. As Jan said, Mergesort has always a complexity of O(n * log n) and Quicksort is up to O(n^2) in worstcase