簡單經過改編的排序算法，你的編譯器能通過嗎？

andalousie

這個演算法是改編的STL的 std::sort的某個實現版本，快排已經改得不是快排了，但是，重要的是，你的編譯器能跟我一樣編譯正常嗎？據我多次嘗試，沒有幾個編譯器會正常。問題可能出在decltype上面，可是我用的有錯嗎？
這裏貼出代碼

1. //Quicksort_Experiment.cpp
   
2. //author: andalousie
   
3. #include <iostream>
   
4. #include <algorithm>
   
5. 
   
6. const int SORT_MAX = 16;
   
7. 
   
8. template<class Ty> inline
   
9. Ty median(Ty a, Ty b, Ty c)
   
10. {
    
11.         if (a < b)
    
12.                 return (b < c ? b : a < c ? c : a);
    
13.         else
    
14.                 return (a < c ? a : b < c ? c : b);
    
15. }
    
16. 
    
17. template<class BI, class T> inline
    
18. void unguarded_insert(BI i2, T v)
    
19. {
    
20.         for (BI scan = i2; v < *(--scan); i2 = scan)
    
21.                 *i2 = *scan;
    
22.         *i2 = v;
    
23. }
    
24. 
    
25. template<class BI> inline
    
26. void insertion_sort(BI i1, BI i2)
    
27. {
    
28.         if (i1 == i2) return;
    
29.         for (BI scan = i1; ++scan != i2; )
    
30.         {
    
31.                 decltype(*i1) v = *scan;
    
32.                 if (!(v < *i1))
    
33.                         unguarded_insert(scan, v);
    
34.                 else
    
35.                 {
    
36.                         std::copy_backward(i1, scan, scan + 1);
    
37.                         *i1 = v;
    
38.                 }
    
39.         }
    
40. }
    
41. 
    
42. template<class It, class T> inline
    
43. void unguarded_partition(It i1, It i2, T pivot)
    
44. {
    
45.         for (; ; ++i1)
    
46.         {
    
47.                 for (; *i1 < pivot; ++i1);
    
48.                 for (; pivot < *(--i2); );
    
49.                 if (i2 < i1)
    
50.                         return;
    
51.                 std::swap(*i1, *i2);
    
52.         }
    
53. }
    
54. 
    
55. template<class It> inline
    
56. void sort(It i1, It i2)
    
57. {
    
58.         if (i2 - i1 <= SORT_MAX)
    
59.                 insertion_sort(i1, i2);
    
60.         else
    
61.         {
    
62.                 int distance = i2 - i1;
    
63.                 for (It s = i1, e; SORT_MAX < distance; )
    
64.                 {
    
65.                         It save;
    
66.                         if (distance >= i2 - s)
    
67.                                 e = i2, distance >>= 1, save = i1;
    
68.                         else
    
69.                                 e = s + distance, save = e;
    
70.                         unguarded_partition(s, e,
    
71.                                 median(*s, *(s + (e - s) / 2), *(e - 1)));
    
72.                         s = save;
    
73.                 }
    
74.                 insertion_sort(i1, i1 + SORT_MAX);
    
75.                 for (i1 += SORT_MAX; i1 != i2; ++i1)
    
76.                         unguarded_insert(i1, *i1);
    
77.         }
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.         int a[] = {1,2,4,3,5,7,0,2,6,4,33,765,345,234,252,23,64,34,54,6,5,3,645,254,234,5,23,25,422,432};
    
83.         sort(a, a+30);
    
84.         for (int i = 0; i < 30; ++i)
    
85.         std::cout << *(a+i) << " ";
    
86. }

复制代码

andalousie

而且這個排序已經不快了。我一開始的目標是不用遞歸實現一下。現在還是有難度