> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/zheng-shu-pai-xu-ii-quicksort-and-mergesort.md).

# 整数排序 II - quick\_sort and merge\_sort

描述

给一组整数，请将其在原地按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(*n* log *n*) 的排序算法。

样例

**例1：**

```
输入：[3,2,1,4,5]，输出：[1,2,3,4,5]。
```

**例2：**

```
输入：[2,3,1]，输出：[1,2,3]。
```

为了对输入的数组进行排序，我们可以使用一个常见的排序算法——快速排序（Quick Sort）。以下是实现此算法的步骤：

1. 确定一个基准点（pivot），可以选择数组的第一个元素。
2. 将数组分成两个子数组，一个包含所有小于基准点的元素，另一个包含所有大于基准点的元素。
3. 对这两个子数组递归地应用上述步骤。
4. 最终将所有子数组合并起来得到排序后的数组。

````
```python
from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @return: nothing
    """
    def sort_integers2(self, a: List[int]):
        # write your code here
        self.quick_partition(a, 0, len(a)-1) #err: len(a)
    
    def quick_partition(self, a: List[int], start:int, end:int):
        if start >= end: # start > end也可以
            return
        pivot = a[(start + end) // 2]
        left, right = start, end
        while left <= right:
            while left <= right and a[left] < pivot: #err: a[left] <= pivot 有大小才有必要换，等于没必要
                left += 1
            while left <= right and a[right] > pivot: #error: a[right] >= pivot
                right -= 1
            if left <= right:
                a[left], a[right] = a[right], a[left]
                left += 1 #err: missing 不要忘了这个
                right -= 1 #err: missing
        self.quick_partition(a, start, right)
        self.quick_partition(a, left, end)
```
````

````
```python
from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @return: nothing
    """
    def sort_integers2(self, a: List[int]):
        # write your code here
        if not a:
            return
        temp = [0] * len(a) #Missing 因为需要合并，一定要有这个Helper array 
        self.merge_sort(a, 0, len(a) - 1, temp)
           
    def merge_sort(self, a:List[int], start: int, end: int, temp: List[int]):
        if start >= end: #递归一定要有程序出口，必须是>= 不能是> ，至少2个数才需要合并
            return 
        mid = (start + end) // 2
        self.merge_sort(a, start, mid, temp)
        self.merge_sort(a, mid + 1, end, temp)
        self.merge(a, start, end, temp)
    
    def merge(self, a:List[int], start: int, end: int, temp: List[int]):
        mid = (start + end) // 2
        left, right = start, mid + 1
        cur = start #ERROR!不能从0开始！！！！！！
        while left <= mid or right <= end:
            if left == mid + 1 and right <= end:
                temp[cur] = a[right]
                right += 1
            elif right == end + 1 and left <= mid:
                temp[cur] = a[left]
                left += 1
            elif a[left] > a[right]:
                temp[cur] = a[right]
                right += 1
            else:
                temp[cur] = a[left]
                left += 1
            cur += 1
        for i in range(start, end+1):
            a[i] = temp[i]


```
````


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/zheng-shu-pai-xu-ii-quicksort-and-mergesort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.