Repository: jerryscript-project/jerryscript
File: jerry-core/ecma/builtin-objects/ecma-builtin-helpers-sort.c (C)

Code before:
 * First  -> array_a_p [left_idx : right_idx - 1]
 * Second -> array_a_p [right_idx : end_idx - 1]
 * Output -> array_b_p
 *
 * @return ecma value
 *         Returned value must be freed with ecma_free_value.
 */
static ecma_value_t
ecma_builtin_helper_array_merge_sort_bottom_up (ecma_value_t *array_a_p, /**< arrays to merge */
                                                uint32_t left_idx, /**< first array begin */
                                                uint32_t right_idx, /**< first array end */
                                                uint32_t end_idx, /**< second array end */
                                                ecma_value_t *array_b_p, /**< output array */
                                                ecma_value_t compare_func, /**< compare function */
                                                const ecma_builtin_helper_sort_compare_fn_t sort_cb) /**< sorting cb */
{
  ecma_value_t ret_value = ECMA_VALUE_EMPTY;
  uint32_t i = left_idx, j = right_idx;

  for (uint32_t k = left_idx; k < end_idx; k++)
  {
    ecma_value_t compare_value = ecma_make_number_value (ECMA_NUMBER_ZERO);

    if (j < end_idx)
    {
      compare_value = sort_cb (array_a_p[i], array_a_p[j], compare_func);
      if (ECMA_IS_VALUE_ERROR (compare_value))
      {
        ret_value = ECMA_VALUE_ERROR;
        break;
      }
    }

    if (i < right_idx && ecma_get_number_from_value (compare_value) <= ECMA_NUMBER_ZERO)
    {
      array_b_p[k] = array_a_p[i];
      i++;
    }
    else
    {
      array_b_p[k] = array_a_p[j];
      j++;
    }
    ecma_free_value (compare_value);
  }

  return ret_value;
} /* ecma_builtin_helper_array_merge_sort_bottom_up */

/**
 * Mergesort function

Review comment (bug):
Shouldn't we also check that `i < right_idx`? It seems to me that otherwise we could end up comparing an element to itself, which I think should be avoided. (e.g. merging `1,3` with `5`, we would compare 1-5, 3-5, and then `i` will overflow the left array, and we compare 5-5, even though the result of the comparision will be unused)

Code after:
 * First  -> source_array_p [left_idx : right_idx - 1]
 * Second -> source_array_p [right_idx : end_idx - 1]
 * Output -> output_array_p
 *
 * @return ecma value
 *         Returned value must be freed with ecma_free_value.
 */
static ecma_value_t
ecma_builtin_helper_array_merge_sort_bottom_up (ecma_value_t *source_array_p, /**< arrays to merge */
                                                uint32_t left_idx, /**< first array begin */
                                                uint32_t right_idx, /**< first array end */
                                                uint32_t end_idx, /**< second array end */
                                                ecma_value_t *output_array_p, /**< output array */
                                                ecma_value_t compare_func, /**< compare function */
                                                const ecma_builtin_helper_sort_compare_fn_t sort_cb) /**< sorting cb */
{
  ecma_value_t ret_value = ECMA_VALUE_EMPTY;
  uint32_t i = left_idx, j = right_idx;

  for (uint32_t k = left_idx; k < end_idx; k++)
  {
    ecma_value_t compare_value = ecma_make_number_value (ECMA_NUMBER_ZERO);

    if (i < right_idx && j < end_idx)
    {
      compare_value = sort_cb (source_array_p[i], source_array_p[j], compare_func);
      if (ECMA_IS_VALUE_ERROR (compare_value))
      {
        ret_value = ECMA_VALUE_ERROR;
        break;
      }
    }

    if (i < right_idx && ecma_get_number_from_value (compare_value) <= ECMA_NUMBER_ZERO)
    {
      output_array_p[k] = source_array_p[i];
      i++;
    }
    else
    {
      output_array_p[k] = source_array_p[j];
      j++;
    }
    ecma_free_value (compare_value);
  }

  return ret_value;
} /* ecma_builtin_helper_array_merge_sort_bottom_up */

/**
 * Mergesort function