排序-归并

归并排序：

分为三步：

1.Divide Step（拆分）

2. Conquer Step（递归）

3.Combine Step（合并）

对数据a[p,r]进行排序：

MERGE-SORT (A, p, r)

1.     IF p < r                                                     // Check for base case
2.         THEN q = FLOOR[(p + r)/2]                 // Divide step
3.                 MERGE-SORT (A, p, q)                 // Conquer step.
4.                 MERGE-SORT (A, q + 1, r)           // Conquer step.
5.                 MERGE (A, p, q, r)                       // Combine step.

MERGE (A, p, q, r )

1.      n1 ← q − p + 1
2.      n2 ← r − q
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞
10.    i ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 1

完整代码：

void mergeSort(int numbers[], int temp[], int array_size)

{
        m_sort(numbers, temp, 0, array_size - 1);

}



void m_sort(int numbers[], int temp[], int left, int right)

{
        int mid;

        if (right > left)

        {

            mid = (right + left) / 2;

            m_sort(numbers, temp, left, mid);

            m_sort(numbers, temp, mid+1, right);


            merge(numbers, temp, left, mid+1, right);

        }

}



void merge(int numbers[], int temp[], int left, int mid, int right)

        {

            int i, left_end, num_elements, tmp_pos;


            left_end = mid - 1;

            tmp_pos = left;

            num_elements = right - left + 1;



while ((left <= left_end) && (mid <= right))

        {

                if (numbers[left] <= numbers[mid])

                {

                        temp[tmp_pos] = numbers[left];

                        tmp_pos = tmp_pos + 1;

                        left = left +1;

                }

                else

                {

                        temp[tmp_pos] = numbers[mid];

                        tmp_pos = tmp_pos + 1;

                        mid = mid + 1;

                }

        }



        while (left <= left_end)

                {

                        temp[tmp_pos] = numbers[left];

                        left = left + 1;

                        tmp_pos = tmp_pos + 1;

                }

                while (mid <= right)

                {

                        temp[tmp_pos] = numbers[mid];

                        mid = mid + 1;

                        tmp_pos = tmp_pos + 1;

                }



                for (i = 0; i <= num_elements; i++)

                {

                        numbers[right] = temp[right];

                        right = right - 1;

                }

        }