# QuickSort

QuickSort is a very famous sort algorithm, `Arrays.sort` is realized by QuickSort.

## Overview

The basic method is following:
1. Choosing a `pivot`, always the lowest value.
2. Dividing the array into two parts, the lower part will be put left of the `pivot`, and the larger part is right.
3. With each round, the `pivot` will move to the final position in the array.
4. Repeat the process, until the sort is completed.

# MergeSort

## Overview

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

## Analysis

In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem.

# Compare

QuickSort has two major deficiencies when compared to mergesort:

1. It’s not stable (as parsifal noted).

2. It doesn’t guarantee n log n performance; it can degrade to quadratic performance on pathological inputs.

and a detailed comparison is following
(From WiKiPedia):

name Best Average Worst Memory Stable
QuickSort nlogn nlogn n^2 logn on average, worst n Typical is no, but stable versions exist
MergeSort nlogn nlogn nlogn n yes