合并排序——消除递归

#include <iostream>

#include <stdlib.h>

#include <algorithm>

#include <set>

#define LEN 20

//Merge sort

void Merge(int *array, int p, int q, int r)
{
     int p1 = 0, p2 = 0;
     int *l1 = new int[q - p];
     int *l2 = new int[r - q];
     for(int i = p; i < q; ++i)
         l1[i - p] = array[i];
     for(int i = q; i < r; ++i)
         l2[i - q] = array[i];
     for(int i = p; i < r; ++i)
     {
         if (p1 == q - p)
         {
             array[i] = l2[p2];
             ++p2;
             continue;
         }
         if (p2 == r - q)
         {
             array[i] = l1[p1];
             ++p1;
             continue;
         }
         if (l1[p1] < l2[p2])
         {
             array[i] = l1[p1];
             ++p1;
         }
         else
         {
             array[i] = l2[p2];
             ++p2;
         }
     }
}

void sort_merge1(int *array, int p, int q)
{
     if (p < q - 1)
     {
         sort_merge1(array, p, (p + q) / 2);
         sort_merge1(array, (p + q) / 2, q);
         Merge(array, p, (p + q) / 2, q);
     }
}

void sort_merge2(int *array, int n)
{
     int len = 1;
     while(len < n)
     { 
         int posEnd = 2, posMid = 1, posStt = 0;
         do
         {
             posMid = (posStt + len > n)?n:posStt + len;
             posEnd = (posMid + len > n)?n:posMid + len;
             Merge(array, posStt, posMid, posEnd);
             posStt = posEnd;
         }while(posEnd < n);
         len *= 2;
     }
}

int main()
{
     int array[LEN];
     for(int i = 0; i < LEN; ++i)
         array[i] = rand() % LEN;
     std::cout << "Before sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
     sort_merge1(array, 0, LEN);
     //sort_merge2(array, LEN);

     std::cout << "After sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
}