C#•15mo ago

❔ 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.

BlazeBin - guvbnmefzrkd

A tool for sharing your source code with the world!

29 Replies

Kaos•15mo ago

Big O tells you how an algorithm scales with input, not about the speed. Quicksort is usually (in practice) faster than merge sort. Also please use something like Benchmark.NET to do performance stuff, timers are not great. try feeding it a list that is sorted in descending order

MyriadColors•15mo ago

Well, in this case the program outright crashed.

Kaos•15mo ago

When the input is ~normally distributed, quick sort should perform better

MyriadColors•15mo ago

When trying the quicksort, that is.

Kaos•15mo ago

that is the worst case for quick sort, so it should be VERY slow, but Merge sort shouldn't be that affected one thing I do notice is that you you are doing a lot with list, but it would be a lot better (and teach you a lot more) if you were doing single element references and logic

MyriadColors•15mo ago

What do you mean?

Kaos•15mo ago

while (left.Count > 0 && right.Count > 0)
    {
        if (left[0] <= right[0])
        {
            output.Add(left[0]);
            left = left.GetRange(1, left.Count - 1);
        }
        else
        {
            output.Add(right[0]);
            right = right.GetRange(1, right.Count - 1);
        }
    }

while (left.Count > 0 && right.Count > 0)
    {
        if (left[0] <= right[0])
        {
            output.Add(left[0]);
            left = left.GetRange(1, left.Count - 1);
        }
        else
        {
            output.Add(right[0]);
            right = right.GetRange(1, right.Count - 1);
        }
    }

instead of get range, tracking where you are in both collections would teach you more whenever you are doing .GetRange, you are creating a new list and giving the GC more work

MyriadColors•15mo ago

Oh, I didn´t know it would create a copy. I thought it would change the lists.

Kaos•15mo ago

This is the meat of that method

List<T> list = new List<T>(count);
Array.Copy(_items, index, list._items, 0, count);
list._size = count;
return list;

List<T> list = new List<T>(count);
Array.Copy(_items, index, list._items, 0, count);
list._size = count;
return list;

MyriadColors•15mo ago

So, what is your suggestion? I am nto ware of another way of doing what I was doing in that while loop.

Kaos•15mo ago

of merging two collections?

MyriadColors•15mo ago

Yes, that code will compare the elements of the lists and merge in ascending order. that´s the meat of the MergeSort

Kaos•15mo ago

I understand what merge sort does. But is there any other way to track elements in a finite amount of collections?

MyriadColors•15mo ago

With a for loop? (im sorry, i am very new at programming)

Kaos•15mo ago

so, instead of tracking the first element of a list, what if you track the first non-processed element?

MyriadColors•15mo ago

I could do a insertion sort on the merged list of left and right? So I would find the unordered elements in the lists and start from there? I take it you mean "unordered" by "non-processed".

Kaos•15mo ago

you can start at the beginning, but move the index variable instead of chopping off the first item always they both may be ordered, so I don't really want to use that term

MyriadColors•15mo ago

Hm, give me a moment to think this through.

Kaos•15mo ago

right, I don't want to tell you the answer, it is counter productive for you

MyriadColors•15mo ago

I udnerstand. So let me try to abstract the details right now: Say I wish to merge and sort two lists: A = [1,2,3] and B = [4,5,6] If I take A[0] and B[0], then the merged list would start with [1,4] and so on until i ave the completed merged list. But if i understand what you mean, you want me to see if A is already ordered, and see if it comes before or after B. So I would just merge them like M = [A,B] instead of "manually" sorting the two arrays into M. Am i on the right track?

Kaos•15mo ago

they both should be ordered already, since, at first you are building the output from a single input

MyriadColors•15mo ago

Right, but they may not be immediate lists like this. i may have [1,3,6] and [10,12,15] right?

Kaos•15mo ago

right, but if you were going to do that by hand, what would you do?

MyriadColors•15mo ago

Do what? Merge? I would see if there si any values in B that belongs in between min(A) and Max(A), fi so I would try to find where exactly that value would fit. If there isn´t, i would need to see if A comes after or before B. I am not sure about the specifics though. (nor if this was what you were askign about)

Kaos•15mo ago

What I would do, is compare the first elements of each. Then I would compare the second element of one to the first of the other

MyriadColors•15mo ago

Hmm, let me come back to this tomorrow, I need to go to sleep rn. In any case, thank you very much. Hopefulyl I will understand with a fresher mind. I´ve been coding all day now lol

Kaos•15mo ago

do take a break, but the key thing I said is with the index

MyriadColors•15mo ago

Ok, I will keep it in mind. I will come back tomorrow to read what you have written again. ty

Accord•15mo ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Weird performance behavior with sorting algorithms.