2_5归并排序

C++实现

class MergeSort {
public:
    void merge(int* A, int l, int mid, int r)
    {
        // start merger
        int tmp[r-l+1];
        int idx = 0;
        int idx_l = l;
        int idx_r = mid;
        while(idx_l < mid && idx_r < r+1){
            if(A[idx_l] < A[idx_r]){
                tmp[idx++] = A[idx_l++];
            }else{
                tmp[idx++] = A[idx_r++];
            }
        }
        
        if(idx_l==mid){
            while(idx_r < r+1){
                tmp[idx++] = A[idx_r++];
            }
        }else{
            while(idx_l < mid){
                tmp[idx++] = A[idx_l++];
            }
        }
        
        idx = 0;
        while(idx < r-l+1){
            A[l+idx] = tmp[idx];
            idx++;
        }
    }
    void process(int* A, int l, int r)
    {
        if(l==r){
            return;
        }
        int mid = (r+l)/2;
        process(A, l, mid);
        process(A, mid+1, r);
        merge(A, l, mid+1, r);
    }
    int* mergeSort(int* A, int n) {
        // write code here
        // if(1==n){
        //     return A;
        // }
        process(A, 0, n-1);
        return A;
    }
};

python 实现

# -*- coding:utf-8 -*-

class MergeSort:
    def mergeSort(self, A, n):
        # write code here
        if 1==n:
            return A
        else:
            mid = n / 2
            A1 = self.mergeSort(A[:mid], mid)
            A2 = self.mergeSort(A[mid:], n-mid)
            result = [0]*(n)
            for i in xrange(n):
                if A1 and A2:
                    if A1[0] < A2[0]:
                        result[i] = A1.pop(0)
                    else:
                        result[i] = A2.pop(0)
                elif not A1:
                    result[i] = A2.pop(0)
                else:
                    result[i] = A1.pop(0)
            return result