Analysis of the Performance Impact of Black-box Randomization for 7 Sorting Algorithms

Abstract: Can black-box randomization change the performance of algorithms? The problem of worst-case behaviour in algorithms is difficult to handle, black-box randomization is one method that has not been rigorously tested. If it could be used to mitigate worst-case behaviour for our chosen algorithms, black-box randomization should be seriously considered for active usage in more algorithms. We have found variables that can be put through a black-box randomizer while our algorithm still gives correct output. These variables have been disturbed and a qualitative manual analysis has been done to observe the performance impact during black-box randomization. This analysis was done for 7 different sorting algorithms using Java openJDK 8. Our results show signs of improvement after black-box randomization, however our experiments showed a clear uncertainty when con- ducting time measurements for sorting algorithms.