0.010.11101001000Merge-insertion - len 2: 12.70Merge-insertion - len 3: 9.33Merge-insertion - len 4: 13.11Merge-insertion - len 5: 12.96Merge-insertion - len 6: 2.65Merge-insertion - len 7: 0.03Merge sort - len 2: 78.57Merge sort - len 3: 27.22Merge sort - len 4: 9.67Merge sort - len 5: 3.77Merge sort - len 6: 1.53Merge sort - len 7: 0.54Merge sort - len 8: 0.24Merge sort - len 9: 0.08Merge sort - len 10: 0.03Merge sort - len 11: 0.01Merge sort - len 12: 0.00Merge sort - len 13: 0.01Quicksort - len 2: 9.43Quicksort - len 3: 3.91Quicksort - len 4: 2.63Quicksort - len 5: 1.89Quicksort - len 6: 1.47Quicksort - len 7: 1.14Quicksort - len 8: 0.98Quicksort - len 9: 0.81Quicksort - len 10: 0.68Quicksort - len 11: 0.52Quicksort - len 12: 0.48Quicksort - len 13: 0.42Quicksort - len 14: 0.37Quicksort - len 15: 0.34Quicksort - len 16: 0.32Quicksort - len 17: 0.25Quicksort - len 18: 0.24Quicksort - len 19: 0.25Quicksort - len 20: 0.22Quicksort - len 21: 0.18Quicksort - len 22: 0.16Quicksort - len 23: 0.15Quicksort - len 24: 0.15Quicksort - len 25: 0.12Quicksort - len 26: 0.13Quicksort - len 27: 0.12Quicksort - len 28: 0.12Quicksort - len 29: 0.10Quicksort - len 30: 0.08Quicksort - len 31: 0.10Quicksort - len 32: 0.08Quicksort - len 33: 0.09Quicksort - len 34: 0.09Quicksort - len 35: 0.06Quicksort - len 36: 0.07Quicksort - len 37: 0.07Quicksort - len 38: 0.07Quicksort - len 39: 0.07Quicksort - len 40: 0.05Quicksort - len 41: 0.05Quicksort - len 42: 0.06Quicksort - len 43: 0.05Quicksort - len 44: 0.05Quicksort - len 45: 0.05Quicksort - len 46: 0.04Quicksort - len 47: 0.04Quicksort - len 48: 0.03Quicksort - len 49: 1.00Insertion sort - len 2: 7.36Insertion sort - len 3: 2.91Insertion sort - len 4: 2.65Insertion sort - len 5: 2.40Insertion sort - len 6: 2.16Insertion sort - len 7: 2.01Insertion sort - len 8: 1.88Insertion sort - len 9: 1.74Insertion sort - len 10: 1.75Insertion sort - len 11: 1.62Insertion sort - len 12: 1.49Insertion sort - len 13: 1.36Insertion sort - len 14: 1.35Insertion sort - len 15: 1.28Insertion sort - len 16: 1.14Insertion sort - len 17: 1.11Insertion sort - len 18: 1.07Insertion sort - len 19: 0.99Insertion sort - len 20: 0.95Insertion sort - len 21: 0.87Insertion sort - len 22: 0.88Insertion sort - len 23: 0.73Insertion sort - len 24: 0.74Insertion sort - len 25: 0.69Insertion sort - len 26: 0.67Insertion sort - len 27: 0.64Insertion sort - len 28: 0.59Insertion sort - len 29: 0.58Insertion sort - len 30: 0.56Insertion sort - len 31: 0.50Insertion sort - len 32: 0.46Insertion sort - len 33: 0.44Insertion sort - len 34: 0.38Insertion sort - len 35: 0.39Insertion sort - len 36: 0.36Insertion sort - len 37: 0.32Insertion sort - len 38: 0.31Insertion sort - len 39: 0.29Insertion sort - len 40: 0.23Insertion sort - len 41: 0.20Insertion sort - len 42: 0.21Insertion sort - len 43: 0.18Insertion sort - len 44: 0.15Insertion sort - len 45: 0.14Insertion sort - len 46: 0.09Insertion sort - len 47: 0.09Insertion sort - len 48: 0.07Insertion sort - len 49: 0.04Stooge sort - len 2: 2687.47Stooge sort - len 3: 3003.41Stooge sort - len 4: 3474.25Stooge sort - len 5: 2146.77Stooge sort - len 6: 44.60Stooge sort - len 7: 14.17Stooge sort - len 8: 5.45Stooge sort - len 9: 1.70Stooge sort - len 10: 0.18Stooge sort - len 11: 0.01Stooge sort - len 12: 0.01Stooge sort - len 13: 0.01Stooge sort - len 14: 0.0225101520253035404549Merge-insertionMerge sortQuicksortInsertion sortStooge sort run length avg runs per permutation (log scale)
Distribution of comparison-access run lengths for five sorting algorithms. A run is a maximal streak of consecutive comparisons that all involve the same element, counted separately per element; runs of length one are excluded. Bars/points show the average number of runs of each length per input, over 1000 random permutations of 50 distinct items.