# 

## 

### 

```c++
template
static void QuickSort(T arr[], int len) {
    quickSort(arr, 0, len - 1);
}

template
static void quickSort(T arr[], int begin, int end) {
    if (begin >= end) {
        return;
    }
    auto pivot = partition(arr, begin, end);
    quickSort(arr, begin, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

template
static int partition(T arr[], int begin, int end) {
    auto base = arr[end];
    auto lessInsert = begin;
    for (int i = begin; i < end; ++i) {
        if (arr[i] < base) {
            swap(arr[lessInsert++], arr[i]);
        }
    }
    swap(arr[lessInsert], arr[end]);
    return lessInsert;
}
```

### 

```c++
template
static void MergeSort(T arr[], int len) {
    auto tmp = new T[len];
    mergeSort(arr, 0, len - 1, tmp);
    delete[] tmp;
}

template
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
    if (begin + 1 >= end) {
        return;
    }

    auto mid = begin + (end - begin) / 2;
    auto begin1 = begin;
    auto end1 = mid;
    auto begin2 = mid + 1;
    auto end2 = end;
    mergeSort(arr, begin1, end1, tmp);
    mergeSort(arr, begin2, end2, tmp);

    // merge two parts
    auto index = begin;
    while (begin1  arr[largest]) {
        largest = right;
    }
    if (largest == root) {
        return;
    }
    swap(arr[largest], arr[root]);
    makeHeap(arr, largest, len);
}
```

## 

[](https://www.cnblogs.com/onepixel/p/7674659.html)

[](https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/er-cha-dui-xiang-jie-shi-xian-you-xian-ji-dui-lie)

## 

- [ ]