diff options
Diffstat (limited to 'common.h')
| -rw-r--r-- | common.h | 28 |
1 files changed, 13 insertions, 15 deletions
@@ -28,22 +28,20 @@ static void swap(char *a, char *b, size_t width) } } -static void reverse(char *base, size_t nmel, size_t width) -{ - char *last = base + (nmel - 1) * width; - while (last > base) { - swap(base, last, width); - base += width; - last -= width; - } -} - /* rotates left */ -static void rotate(char *base, size_t nmel, size_t width, size_t shift) +static void rotate(char *base, size_t size, size_t shift) { - reverse(base, shift, width); - reverse(base + shift * width, nmel - shift, width); - reverse(base, nmel, width); + int dir = 1; + while (shift) { + while (2*shift <= size) { + swap(base, base + dir*shift, shift); + size -= shift; + base += shift*dir; + } + shift = size - shift; + base = dir > 0 ? base + size - shift : base - shift; + dir *= -1; + } } static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp) @@ -55,7 +53,7 @@ static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_ for (; insertpos < sortnmel && cmp(base, sorted + insertpos * width) > 0; insertpos++); if (insertpos > 0) { - rotate(base, bufnmel + insertpos, width, bufnmel); + rotate(base, (bufnmel + insertpos) * width, bufnmel * width); } base += (insertpos + 1) * width; |