void _quickSort()

in lib/src/algorithms.dart [421:461]

• 41 lines of code
• 6 McCabe index (conditional complexity)

void _quickSort<E, K>(List<E> list, K Function(E element) keyOf,
    int Function(K a, K b) compare, Random random, int start, int end) {
  const minQuickSortLength = 24;
  var length = end - start;
  while (length >= minQuickSortLength) {
    var pivotIndex = random.nextInt(length) + start;
    var pivot = list[pivotIndex];
    var pivotKey = keyOf(pivot);
    var endSmaller = start;
    var startGreater = end;
    var startPivots = end - 1;
    list[pivotIndex] = list[startPivots];
    list[startPivots] = pivot;
    while (endSmaller < startPivots) {
      var current = list[endSmaller];
      var relation = compare(keyOf(current), pivotKey);
      if (relation < 0) {
        endSmaller++;
      } else {
        startPivots--;
        var currentTarget = startPivots;
        list[endSmaller] = list[startPivots];
        if (relation > 0) {
          startGreater--;
          currentTarget = startGreater;
          list[startPivots] = list[startGreater];
        }
        list[currentTarget] = current;
      }
    }
    if (endSmaller - start < end - startGreater) {
      _quickSort(list, keyOf, compare, random, start, endSmaller);
      start = startGreater;
    } else {
      _quickSort(list, keyOf, compare, random, startGreater, end);
      end = endSmaller;
    }
    length = end - start;
  }
  _movingInsertionSort<E, K>(list, keyOf, compare, start, end, list, start);
}