Why is quick sort and merge sort called stable algorithms?

Answer 1

Quick sort is not stable, but stable versions do exist. This comes at a cost in performance, however.

A stable sort maintains the order of equal elements. That is, equal elements remain in the same order they were input. An unstable sort may change the order. In some cases, the order of equal elements is of no consequence, but when two elements with different values have the same sort key, then order can be important.

Answer 2

Yes. If you are having problems do a manual bounds check. Also ensure that the user supplied function is not causing problems.

No. While its average cost if O(nlogn), its worst case cost is O(n2)

Ok someone is taking computer science. Cost has nothing to do with stability (from the computer science aspect) but everything to do with the pivot point as far as quicksort is concerned. Depending on how the pivot point is implemented dictates if quicksort is stable or not. Stable or not quicksort is a good all round sort routine, usually not the quickest or slowest. The speed of any sorting algorithm is dependent on what data the algorithm is required to sort and also the number of elements to be sorted.

It should be noted that the qsort function (usually assumed to be quick sort) does not necessarily implement the quicksort algorithm. The algorithm behind qsort is up to the library manufacturer.

From a practical standpoint with the average program cost is not the issue. Cost becomes an issue if there are performance problems. Performance problems can (usually) be kept at bay by sorting pointers (4 bytes) to data rather than sorting data (that can be very big).

Answer 3

The Quick Sort Method, however fast on average, has a bad worst case scenario. If for instance the list you sort is already sorted or oppositely sorted, the time for Quick Sort may be n*n in stead of n*log(n) - which in effect makes it as slow as the most simple sort method, Bubble Sort. Even when programmers change the routine so that exactly these worst cases will not occur, there will always be other possible lists that will slow down the Quick Sort.

Merge Sort, which is also n*log(n), does not have this worst case scenario. On average it's hardly slower (if at all) than Quick Sort, but it's far more stable in keeping that speed at all times.

Answer 4

Quick Sort is an "average" performing sorting algorithm; there are better algorithms out there, but it is considered the best of the "learner's algorithms" (generally implied to be quick sort, bubble sort, selection sort, and gnome sort). It has a medium-length average sorting time, which is faster than bubble sorting and gnome sorting, but also has a medium-length best-case sorting time, with bubble sorting and gnome sorting beating it speed-wise. It also has a higher memory overhead than in-place swapping algorithms such as bubble sort and gnome sort.