> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/sort.md).

# 11. Sort

## Sorting

Java use modified mergesort by java.util.Collections.sort to sort object

* Guarantees O(nlogn) performance and O(n) extra space
* Stable in all kinds of input

Java use quicksort in java.util.Arrays.sort

* Avarage less than O(nlogn), worst case O(n^2)
* Average O(logn) extra space, worst case O(n/2) extra space
* Stable only in primitive type

[Reference](http://stackoverflow.com/questions/15154158/why-collections-sort-uses-merge-sort-instead-of-quicksort)

## Quicksort

```java
private static int partition(int[] arr, int left, int right){
    int pivot = arr[right];
    int i = left; // index small or equal to left

    for (int j = left; j < right; j++){
        if (arr[j] <= pivot){
            // swap
            swap(arr, i ,j);
            i++;
        }
    }

    // swap pivot value and i index value;
    swap(arr, i, right);
    return i;
}

private static void quickSort(int[] arr, int left, int right){
    if (left < right){
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }
}
```