# 排序

### 1. 题目

给定一个数组，请你编写一个函数，返回该数组排序后的形式。示例1

### 输入

复制

```
[5,2,3,1,4]
```

### 返回值

复制

```
[1,2,3,4,5]
```

示例2

### 输入

复制

```
[5,1,6,2,5]
```

### 返回值

复制

```
[1,2,5,5,6]
```

### 2. 思路

1. merge sort
2. Time O(nlogn) , O(n) for merging in each level, O(logn) for iterating the whole tree. so O(nlogn)
3.  Space O(n),  我们要在每一个层把sorted 好的element存起来，然后再去另外一个分支进行divide，最坏情况就是把所有的node的value存起来 O(n)，然后再加上recursion的层数的space O(logn),所有O(n) +O(logn)  = O(n)

```
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr ):
        # write code here
        # use merge sort
        # 1. input: arr unsorted,  output: sorted array
        # 2. idea: merge sort
        #     1. divide array into left, right subarray
        #     2. if can not divide, return list of the only one element
        #     3. merge left, right sublist and sort
        #
        # Time: O(nlogn),  O(n) for merging, logn for dividing to recurision
        #Space :O(n)  O(n) for storing merge sorted array
        if not arr:
            return None
        #divide 
        return self.mergesort(arr, 0 , len(arr)-1)
    def mergesort(self, arr, start, end):
        if start >=end:
            return [arr[end]]
        mid = (start +end)//2
        l_arr = self.mergesort(arr, start, mid)
        r_arr =  self.mergesort(arr, mid+1, end)
        #merge 
        return self.merge(l_arr, r_arr)
    def merge(self, l_arr, r_arr):
        if not l_arr:
            return r_arr
        if not r_arr:
            return l_arr
        res = []
        l_pt, r_pt = 0,0
        while l_pt <len(l_arr) and r_pt < len(r_arr):
            if l_arr[l_pt] < r_arr[r_pt]:
                res.append(l_arr[l_pt])
                l_pt += 1
            else:
                res.append(r_arr[r_pt])
                r_pt += 1
        if l_pt < len(l_arr):
            res.extend(l_arr[l_pt:])
        if r_pt < len(r_arr):
            res.extend(r_arr[r_pt:])
        return res
            
```


---

# Agent Instructions: 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://wenkangwei.gitbook.io/leetcode-notes/datastructure/sorting/pai-xu.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.