# Summary

**1.Array memory space complexity:**

Quick sort :O(1)

Merge sort: O(n)

Heap sort: O(n)

**2.Quick Sort VS Merge Sort**

Quick sort:先全局有序再局部有序

Merge sort: 先局部有序再全局有序

1>都是Divided conquer算法

2> Space complexity: O(1) VS O(n)

3>Quick sort是不稳定排序，merge sort 是稳定排序

4> Quick sort 平均时间为O(nlogn), Merge sort最好最坏为O(nlogn)

**Quick Sort:**

```
/* This function takes mid element as pivot, places the pivot element at its
       correct position in sorted array, and places all smaller (smaller than pivot)
       to left of pivot and all greater elements to right of pivot */
    public static int partition(int[] arr,int left,int right)
    {
        int i=left;
        int j=right;
        int temp;
        int pivot= arr[(left+right)/2];


        while(i<=j)
        {
            while(arr[i]<pivot)
                i++;
            while(arr[j]>pivot)
                j--;

            if(i<=j)
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
                j--;
            }
        }

        return i;

    }

    public static void quickSort(int[] arr,int left,int right)
    {
        int index=partition(arr,left,right);

        if(left<index-1)
        {
            quickSort(arr,left,index-1);
        }
        if(right>index)
        {
            quickSort(arr,index,right);
        }
    }
```

**partition 函数模板：**

```
int partition(int[] nums, int lo, int hi) {
    if (lo == hi) return lo;
    // 将 nums[lo] 作为默认分界点 pivot
    int pivot = nums[lo];
    // j = hi + 1 因为 while 中会先执行 --
    int i = lo, j = hi + 1;
    while (true) {
        // 保证 nums[lo..i] 都小于 pivot
        while (nums[++i] < pivot) {
            if (i == hi) break;
        }
        // 保证 nums[j..hi] 都大于 pivot
        while (nums[--j] > pivot) {
            if (j == lo) break;
        }
        if (i >= j) break;
        // 如果走到这里，一定有：
        // nums[i] > pivot && nums[j] < pivot
        // 所以需要交换 nums[i] 和 nums[j]，
        // 保证 nums[lo..i] < pivot < nums[j..hi]
        swap(nums, i, j);
    }
    // 将 pivot 值交换到正确的位置
    swap(nums, j, lo);
    // 现在 nums[lo..j-1] < nums[j] < nums[j+1..hi]
    return j;
}

// 交换数组中的两个元素
void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
```

**Merge Sort:**

```
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
    static void merge(int[] arr,int l,int m,int r)
    {
        int i,j,k;
        int n1=m-l+1;
        int n2=r-m;


        /* create temp arrays */
        int[] L=new int[n1];
        int[] R=new int[n2];


        /* Copy data to temp arrays L[] and R[] */
        for(i=0;i<n1;i++)
        {
            L[i]=arr[l+i];
        }
        for(j=0;j<n2;j++)
        {
            R[j]=arr[m+1+j];
        }


        /* Merge the temp arrays back into arr[l..r]*/
        i=0;
        j=0;
        k=l;



        while(i<n1 && j<n2)
        {
            if(L[i]<=R[j])
            {
                arr[k]=L[i];
                i++;
            }
            else
            {
                arr[k]=R[j];
                j++;
            }
            k++;
        }
        /* Copy the remaining elements of L[], if there are any */
        while(i<n1)
        {
            arr[k]=L[i];
            i++;
            k++;
        }
        /* Copy the remaining elements of R[], if there are any */
        while(j<n2)
        {
            arr[k]=R[j];
            j++;
            k++;
        }


    }



    /* l is for left index and r is right index of the sub-array
      of arr to be sorted */
    static void mergesort(int[] arr,int l,int r)
    {
        if(l<r)
        {
            int m=(l+r)/2;
            mergesort(arr,l,m);
            mergesort(arr,m+1,r);
            merge(arr,l,m,r);
        }
    }
```


---

# 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://junnie.gitbook.io/nine-chapter/6.array/summary.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.