| 1003 | // with compile-time element size + typed comparator. |
| 1004 | template <typename T, typename Compare> |
| 1005 | inline void das_stable_sort(T *first, T *last, Compare cmp) |
| 1006 | { |
| 1007 | if (last - first <= 1) return; |
| 1008 | size_t nel = size_t(last - first); |
| 1009 | T *data = first; |
| 1010 | T *buf = (T *)malloc(nel * sizeof(T)); |
| 1011 | if (!buf) { das_sort(first, last, cmp); return; } // OOM → unstable fallback |
| 1012 | size_t maxRuns = nel / DAS_STABLE_MINRUN + 2; |
| 1013 | size_t *bndA = (size_t *)malloc((maxRuns + 1) * sizeof(size_t)); |
| 1014 | size_t *bndB = (size_t *)malloc((maxRuns + 1) * sizeof(size_t)); |
| 1015 | if (!bndA || !bndB) { free(bndA); free(bndB); free(buf); das_sort(first, last, cmp); return; } |
| 1016 | |
| 1017 | size_t *cur = bndA, *nxt = bndB; |
| 1018 | size_t nb = 0; |
| 1019 | cur[nb++] = 0; |
| 1020 | size_t i = 0; |
| 1021 | while (i < nel) { |
| 1022 | size_t runStart = i, j = i + 1; |
| 1023 | if (j < nel) { |
| 1024 | if (cmp(data[j], data[i])) { // strictly descending |
| 1025 | j++; |
| 1026 | while (j < nel && cmp(data[j], data[j - 1])) j++; |
| 1027 | using std::swap; |
| 1028 | for (size_t a = runStart, b = j - 1; a < b; a++, b--) swap(data[a], data[b]); |
| 1029 | } else { // non-decreasing |
| 1030 | j++; |
| 1031 | while (j < nel && !cmp(data[j], data[j - 1])) j++; |
| 1032 | } |
| 1033 | } |
| 1034 | if (j - runStart < DAS_STABLE_MINRUN) { |
| 1035 | size_t hi = (runStart + DAS_STABLE_MINRUN < nel) ? runStart + DAS_STABLE_MINRUN : nel; |
| 1036 | das_stable_insertion_run_t(data, runStart, hi, cmp); |
| 1037 | j = hi; |
| 1038 | } |
| 1039 | cur[nb++] = j; |
| 1040 | i = j; |
| 1041 | } |
| 1042 | |
| 1043 | T *src = data, *dst = buf; |
| 1044 | while (nb - 1 > 1) { |
| 1045 | size_t R = nb - 1, nn = 0, t = 0; |
| 1046 | nxt[nn++] = 0; |
| 1047 | for (; t + 1 < R; t += 2) { |
| 1048 | das_stable_merge_runs_t(src, dst, cur[t], cur[t + 1], cur[t + 2], cmp); |
| 1049 | nxt[nn++] = cur[t + 2]; |
| 1050 | } |
| 1051 | if (t < R) { |
| 1052 | memcpy(&dst[cur[t]], &src[cur[t]], (cur[t + 1] - cur[t]) * sizeof(T)); |
| 1053 | nxt[nn++] = cur[t + 1]; |
| 1054 | } |
| 1055 | T *ts = src; src = dst; dst = ts; |
| 1056 | size_t *tb = cur; cur = nxt; nxt = tb; |
| 1057 | nb = nn; |
| 1058 | } |
| 1059 | if (src != data) memcpy(data, src, nel * sizeof(T)); |
| 1060 | |
| 1061 | free(bndA); free(bndB); free(buf); |
| 1062 | } |
no test coverage detected