human
I am working on the file "03_BinaryTree_DivideConquer.ipynb".
The first task is:
Quick Sort vs Merge Sort
比较快速排序与归并排序的联系与区别：
时间复杂度：都是 O(nlogn) 但是快速排序是平均 O(nlogn)，归并排序是最好最坏都是 O(nlogn)
空间复杂度：快速排序耗费 O(1) 的额外空间，归并排序不得不耗费 O(n) 的额外空间。
排序稳定性：快速排序是不稳定的排序算法。归并排序是稳定的排序算法。http://baike.baidu.com/view/547325.htm 
分治的思想：快速排序先整体有序再局部有序。归并排序先局部有序再整体有序。

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

https://www.lintcode.com/en/problem/sort-integers-ii/
Can you write Python program for it?
assistant
#Here is the Python program you requested.

## Quick Sort

class Solution:
    # @param {int[]} A an integer array
    # @return nothing
    def sortIntegers2(self, A):
        # Write your code here
        
        def quicksort(A, start, end):
            if start >= end:
                return 
        
            left, right = start, end
            # pivot, the middle value, not A[0], A[-1]
            pivot = A[start + (end-start)/2]                 # get the value not the index
            while left <= right:                             # here is left <= right, not <, aviod overflow!!
                while left <= right and A[left] < pivot:     # here is A[left] < pivot, not <=, allocation is more homogeneous
                    left += 1
                while left <= right and A[right] > pivot:
                    right -= 1
                if left <= right:
                    A[left], A[right] = A[right], A[left]
                    left += 1
                    right -= 1
            
            quicksort(A, start, right)
            quicksort(A, left, end)
        
        if A is None or len(A) == 0:
            return
        quicksort(A, 0, len(A)-1)

## Merge Sort

class Solution:
    # @param {int[]} A an integer array
    # @return nothing
    def sortIntegers2(self, A):
        # Write your code here
        
        
        def mergeSort(A, start, end, temp):
            if start >= end:
                return
            mergeSort(A, start, (start + end)/2, temp)
            mergeSort(A, (start + end)/2 + 1, end, temp)
            merge(A, start, end, temp)
            
        def merge(A, start, end, temp):
            mid = (start + end)/2
            leftstart, rightstart = start, mid+1
            tempstart = start
            while leftstart <= mid and rightstart <= end:
                if A[leftstart] <= A[rightstart]:
                    temp[tempstart] = A[leftstart]
                    leftstart += 1
                else:
                    temp[tempstart] = A[rightstart]
                    rightstart += 1
        ...