V8 Array::sort; -m64 -std=c99 Playing around 100000 length list: ~7ms with -O3, ~16ms without, and about 7 seconds in javascript

GenericSort.c

int GenericSort(void **list, size_t length, compareFn compare) {

  // Compare the list as ptrdiff_t's if no comparator is specified.
  if (!compare) {
    int basic_compare(void *a, void *b) {
      int result = 0;
      // Compare as signed
      ptrdiff_t aL = (ptrdiff_t)a;
      ptrdiff_t bL = (ptrdiff_t)b;
      if (aL < bL) {
        result = -1;
      }
      if (aL > bL) {
        result = 1;
      }
      return result;
    };
    compare = basic_compare;
  }

  // Use InsertionSort for tiny lists
  void InsertionSort(size_t from, size_t to) {
    ptrdiff_t fromCmp = (ptrdiff_t)from;
    ptrdiff_t toCmp = (ptrdiff_t)to;
    for (ptrdiff_t i = fromCmp + 1; i < toCmp; ++i) {
      void *element = list[i];
      ptrdiff_t j;
      for (j = i - 1; j >= fromCmp; --j) {
        void *tmp = list[j];
        int order = compare(tmp, element);
        if (order > 0) {
          list[j + 1] = tmp;
        } else {
          break;
        }
      }
      list[j + 1] = element;
    }
  };

  // Find a well-distributed pivot for larger arrays by sampling
  size_t GetThirdIndex(size_t from, size_t to) {
    // Build an array of evenly distributed samples
    size_t increment = 200u + ((to - from) & 15ull);
    size_t candidates_length = 1 + (to - from - 2) / increment;
    size_t *candidates = (size_t *)malloc(sizeof(size_t) * candidates_length);
    size_t j = 0;
    for (size_t i = from + 1; i < to - 1; i += increment) {
      candidates[j] = i;
      j += 1;
    }
    // Sort the array using the original comparator
    int candidate_sort(void *a, void *b) {
      return compare(list[(size_t)a], list[(size_t)b]);
    };
    GenericSort((void **)candidates, j, candidate_sort);
    // Return the median index
    size_t third_index = candidates[j >> 1];
    free(candidates);
    return third_index;
  };

  void QuickSort(size_t from, size_t to) {
    size_t third_index = 0;
    while(1) {
      if (to - from <= 10) {
        return InsertionSort(from, to);
      }
      if (to - from > 1000) {
        third_index = GetThirdIndex(from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last, third
      void *v0 = list[from];
      void *v1 = list[to - 1];
      void *v2 = list[third_index];
      int c01 = compare(v0, v1);
      if (c01 > 0) {
        void *tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1
      int c02 = compare(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1
        void *tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        int c12 = compare(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          void *tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      list[from] = v0;
      list[to - 1] = v2;
      void *pivot = v1;
      size_t low_end = from + 1;   // Upper bound of elements lower than pivot.
      size_t high_start = to - 1;  // Lower bound of elements greater than pivot.
      list[third_index] = list[low_end];
      list[low_end] = pivot;

      for (size_t i = low_end + 1; i < high_start; ++i) {
        void *element = list[i];
        int order = compare(element, pivot);
        if (order < 0) {
          list[i] = list[low_end];
          list[low_end] = element;
          low_end += 1;
        } else if (order > 0) {
          do {
            high_start -= 1;
            if (high_start == i) goto partition;
            void *top_elem = list[high_start];
            order = compare(top_elem, pivot);
          } while (order > 0);
          list[i] = list[high_start];
          list[high_start] = element;
          if (order < 0) {
            element = list[i];
            list[i] = list[low_end];
            list[low_end] = element;
            low_end += 1;
          }
        }
        partition: continue;
      }
      if (to - high_start < low_end - from) {
        QuickSort(high_start, to);
        to = low_end;
      } else {
        QuickSort(from, low_end);
        from = high_start;
      }
    }
  }

  if (length < 2) return 0;

  QuickSort(0, length);

  return 0;
}