❔ Weird performance behavior with sorting algorithms.
I´ve been writing different sorting algorithms as exercises to learn C# (and algorithms in general). I´ve been testing them on an array of 100 thousand long unique numbers generated by the program every time it is run. The code is as follows:
https://paste.mod.gg/guvbnmefzrkd/0
As far as my understanding of algorithms go, my Naive QuickSort and the MergeSort should have the same average time complexity of O(n * log n), I know the worst-case for QuickSort (having a pivot of the biggest value in the array) is extremely unlikely to happen given the dataset (but do correct me if im wrong, please). So i expected both algorithms to have roughly the same performance.
However, according to my execution time measurements (you can measure yourself witht he code i´ve provided) the MergeSort code was substantially slower compared to the QuickSort.
For example, my quickSort algorithm takes about 40-50ms (in average) to sort the 100k long array, while the Mergesort takes between 1.5 and 2 sconds.
Since I am not well-versed in algorithms and how they work, I am at a loss to explain this large of a differential. I believe it is due to the distribution patterns of the random arrays I am creating with my generateUniqueList function, but I dont know what would it be.
Thank you for the help.
https://paste.mod.gg/guvbnmefzrkd/0
As far as my understanding of algorithms go, my Naive QuickSort and the MergeSort should have the same average time complexity of O(n * log n), I know the worst-case for QuickSort (having a pivot of the biggest value in the array) is extremely unlikely to happen given the dataset (but do correct me if im wrong, please). So i expected both algorithms to have roughly the same performance.
However, according to my execution time measurements (you can measure yourself witht he code i´ve provided) the MergeSort code was substantially slower compared to the QuickSort.
For example, my quickSort algorithm takes about 40-50ms (in average) to sort the 100k long array, while the Mergesort takes between 1.5 and 2 sconds.
Since I am not well-versed in algorithms and how they work, I am at a loss to explain this large of a differential. I believe it is due to the distribution patterns of the random arrays I am creating with my generateUniqueList function, but I dont know what would it be.
Thank you for the help.
A tool for sharing your source code with the world!
