44 // means that this method not only returns the index of the pivot |
44 // means that this method not only returns the index of the pivot |
45 // element. It also alters the array so that: |
45 // element. It also alters the array so that: |
46 // array[first] <= array[middle] <= array[last] |
46 // array[first] <= array[middle] <= array[last] |
47 // A side effect of this is that arrays of length <= 3 are sorted. |
47 // A side effect of this is that arrays of length <= 3 are sorted. |
48 template<class T, class C> |
48 template<class T, class C> |
49 static int find_pivot(T* array, int length, C comparator) { |
49 static size_t find_pivot(T* array, size_t length, C comparator) { |
50 assert(length > 1, "length of array must be > 0"); |
50 assert(length > 1, "length of array must be > 0"); |
51 |
51 |
52 int middle_index = length / 2; |
52 size_t middle_index = length / 2; |
53 int last_index = length - 1; |
53 size_t last_index = length - 1; |
54 |
54 |
55 if (comparator(array[0], array[middle_index]) == 1) { |
55 if (comparator(array[0], array[middle_index]) > 0) { |
56 swap(array, 0, middle_index); |
56 swap(array, 0, middle_index); |
57 } |
57 } |
58 if (comparator(array[0], array[last_index]) == 1) { |
58 if (comparator(array[0], array[last_index]) > 0) { |
59 swap(array, 0, last_index); |
59 swap(array, 0, last_index); |
60 } |
60 } |
61 if (comparator(array[middle_index], array[last_index]) == 1) { |
61 if (comparator(array[middle_index], array[last_index]) > 0) { |
62 swap(array, middle_index, last_index); |
62 swap(array, middle_index, last_index); |
63 } |
63 } |
64 // Now the value in the middle of the array is the median |
64 // Now the value in the middle of the array is the median |
65 // of the fist, last and middle values. Use this as pivot. |
65 // of the fist, last and middle values. Use this as pivot. |
66 return middle_index; |
66 return middle_index; |
67 } |
67 } |
68 |
68 |
69 template<class T, class C, bool idempotent> |
69 template<bool idempotent, class T, class C> |
70 static int partition(T* array, int pivot, int length, C comparator) { |
70 static size_t partition(T* array, size_t pivot, size_t length, C comparator) { |
71 int left_index = -1; |
71 size_t left_index = 0; |
72 int right_index = length; |
72 size_t right_index = length - 1; |
73 T pivot_val = array[pivot]; |
73 T pivot_val = array[pivot]; |
74 |
74 |
75 while (true) { |
75 for ( ; true; ++left_index, --right_index) { |
76 do { |
76 for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) { |
77 left_index++; |
77 assert(left_index < length, "reached end of partition"); |
78 } while (comparator(array[left_index], pivot_val) == -1); |
78 } |
79 do { |
79 for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) { |
80 right_index--; |
80 assert(right_index > 0, "reached start of partition"); |
81 } while (comparator(array[right_index], pivot_val) == 1); |
81 } |
82 |
82 |
83 if (left_index < right_index) { |
83 if (left_index < right_index) { |
84 if (!idempotent || comparator(array[left_index], array[right_index]) != 0) { |
84 if (!idempotent || comparator(array[left_index], array[right_index]) != 0) { |
85 swap(array, left_index, right_index); |
85 swap(array, left_index, right_index); |
86 } |
86 } |
91 |
91 |
92 ShouldNotReachHere(); |
92 ShouldNotReachHere(); |
93 return 0; |
93 return 0; |
94 } |
94 } |
95 |
95 |
96 template<class T, class C, bool idempotent> |
96 template<bool idempotent, class T, class C> |
97 static void inner_sort(T* array, int length, C comparator) { |
97 static void inner_sort(T* array, size_t length, C comparator) { |
98 if (length < 2) { |
98 if (length < 2) { |
99 return; |
99 return; |
100 } |
100 } |
101 int pivot = find_pivot(array, length, comparator); |
101 size_t pivot = find_pivot(array, length, comparator); |
102 if (length < 4) { |
102 if (length < 4) { |
103 // arrays up to length 3 will be sorted after finding the pivot |
103 // arrays up to length 3 will be sorted after finding the pivot |
104 return; |
104 return; |
105 } |
105 } |
106 int split = partition<T, C, idempotent>(array, pivot, length, comparator); |
106 size_t split = partition<idempotent>(array, pivot, length, comparator); |
107 int first_part_length = split + 1; |
107 size_t first_part_length = split + 1; |
108 inner_sort<T, C, idempotent>(array, first_part_length, comparator); |
108 inner_sort<idempotent>(array, first_part_length, comparator); |
109 inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator); |
109 inner_sort<idempotent>(&array[first_part_length], length - first_part_length, comparator); |
110 } |
110 } |
111 |
111 |
112 public: |
112 public: |
113 // The idempotent parameter prevents the sort from |
113 // The idempotent parameter prevents the sort from |
114 // reordering a previous valid sort by not swapping |
114 // reordering a previous valid sort by not swapping |
115 // fields that compare as equal. This requires extra |
115 // fields that compare as equal. This requires extra |
116 // calls to the comparator, so the performance |
116 // calls to the comparator, so the performance |
117 // impact depends on the comparator. |
117 // impact depends on the comparator. |
118 template<class T, class C> |
118 template<class T, class C> |
119 static void sort(T* array, int length, C comparator, bool idempotent) { |
119 static void sort(T* array, size_t length, C comparator, bool idempotent) { |
120 // Switch "idempotent" from function paramter to template parameter |
120 // Switch "idempotent" from function paramter to template parameter |
121 if (idempotent) { |
121 if (idempotent) { |
122 inner_sort<T, C, true>(array, length, comparator); |
122 inner_sort<true>(array, length, comparator); |
123 } else { |
123 } else { |
124 inner_sort<T, C, false>(array, length, comparator); |
124 inner_sort<false>(array, length, comparator); |
125 } |
125 } |
126 } |
126 } |
127 }; |
127 }; |
128 |
128 |
129 |
129 |