归并排序

 1  template <typename Comparable>
 2 void mergeSort(vector<Comparable>&a)
 3 {
 4 　　mergeSort(a,0,a.size()-1);
 5 }
 6 
 7 template <typename Comparable>
 8 void mergeSort(vector<Comparable>&a,int left, int right)
 9 {
10 　　if (left < right)
11 　　{
12 　　　　int mid = (left + right)/2;
13 　　　　mergeSort(a,left, mid);
14 　　　　mergeSort(a,left, mid+1,right);
15 　　}
16 }
17 
18 template <typename Comparable>
19 void merge (vector<Comparable&a, int leftStart, int rightStart, int rightEnd)
20 {
21 　　int leftEnd = rightStart - 1;
22 　　int numElements = rightEnd - leftStart + 1;
23 　　vector<Comparable>temp(numElements);
24 　　int indexTemp = 0;
25 　　int tempLeftStart = leftStart;
26 　　while ( leftStart <= leftEnd && rightStart <= rightEnd )
27 　　{
28 　　　　if ( a[leftStart] <= a[rightStart] )
29 　　　　　　temp[indexTemp++] = a[leftStart++];
30 　　　　else
31 　　　　　　temp[indexTemp++] = a[rightStart++];
32 　　}
33 　　while ( leftStart <= leftEnd )
34 　　　　temp[indexTemp++] = a[leftStart++];
35 　　while ( rightStart <= rightEnd )
36 　　　　temp[indexTemp++] = a[rightStart++];
37 　　for ( int i = 0; i < numElements; ++i )
38 　　　　　　a[tempLeftStart + i] = temp[i];
39 }