To add to BrowserUK's answer, mergesort is stable, producing the original order for items that compare equal. Quicksort is not stable, the sorted order is scrambled for equal items.

In the perl 5.8.0 source tree, the sort algorithm is found in pp_sort.c. That file has unusually good comments in it. Here is the meat of perl's top level sort function, Perl_sortsv():

    hints = SORTHINTS(hintsv);
    if (hints & HINT_SORT_QUICKSORT) {
    sortsvp = S_qsortsv;
    }
    else {
    /* The default as of 5.8.0 is mergesort */
    sortsvp = S_mergesortsv;
    }

    sortsvp(aTHX_ array, nmemb, cmp);
[download]

After Compline,
Zaxo