Exit quicksort earlier
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/38422d12 Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/38422d12 Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/38422d12 Branch: refs/heads/master Commit: 38422d12ca5ebf1e98b2c6a582a1e872d8da3fa7 Parents: 27707a3 Author: Nick Wellnhofer <[email protected]> Authored: Sun Apr 26 19:11:35 2015 +0200 Committer: Nick Wellnhofer <[email protected]> Committed: Sun Apr 26 19:45:01 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Util/SortUtils.c | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/38422d12/runtime/core/Clownfish/Util/SortUtils.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Util/SortUtils.c b/runtime/core/Clownfish/Util/SortUtils.c index 3137531..31f5b77 100644 --- a/runtime/core/Clownfish/Util/SortUtils.c +++ b/runtime/core/Clownfish/Util/SortUtils.c @@ -278,6 +278,12 @@ SI_choose_pivot4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right, static void S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right, CFISH_Sort_Compare_t compare, void *context) { + if (right <= left) { return; } + + /* TODO: A standard optimization for quicksort is to fall back to an + * insertion sort when the the number of elements to be sorted becomes + * small enough. */ + FOUR_BYTE_TYPE *const pivot = SI_choose_pivot4(elems, left, right, compare, context); int32_t i = left; @@ -285,12 +291,6 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right, int32_t p = left; int32_t q = right - 1; - if (right <= left) { return; } - - /* TODO: A standard optimization for quicksort is to fall back to an - * insertion sort when the the number of elements to be sorted becomes - * small enough. */ - while (1) { int comparison1; int comparison2; @@ -386,6 +386,12 @@ SI_choose_pivot8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right, static void S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right, CFISH_Sort_Compare_t compare, void *context) { + if (right <= left) { return; } + + /* TODO: A standard optimization for quicksort is to fall back to an + * insertion sort when the the number of elements to be sorted becomes + * small enough. */ + EIGHT_BYTE_TYPE *const pivot = SI_choose_pivot8(elems, left, right, compare, context); int32_t i = left; @@ -393,12 +399,6 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right, int32_t p = left; int32_t q = right - 1; - if (right <= left) { return; } - - /* TODO: A standard optimization for quicksort is to fall back to an - * insertion sort when the the number of elements to be sorted becomes - * small enough. */ - while (1) { int comparison1; int comparison2;
