In selection sort, descending array's performance is faster than ascending array. why?

Question

I ran selection sort algorithm with a sorted array(ascending order) and a unsorted array(decending order) in C visual studio. The result was performance of a unsorted array is faster than one of a sorted array in large size.

I think it's very ridiculous. Doesn't selection sort always take constant time depends on array size? Why is this??

This is selectionsort. And I ran this with n = 100,000 to 1,000,000. I increased it by 100,000 for every run.

int main() {
    int array[1000000]; //1,000,000
    int i = 100000; //100,000
    int n = 100000; //100,000
    for (int k = 0; k < 10; ++k) {
        insert_ascending(array, n); //stuff elements in ascending order
        //time check
        sort(array, n);

        insert_decending(array, n); //stuff elements in descending order
        //time check
        sort(array, n);

        n += i;
    }
}
void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    } 
}

`Doesn't selection sort always take constant time depends on array size?` - [no](https://stackoverflow.com/q/11227809/11683). — GSerg, Sep 13 '20 at 14:58
For any meaningful response to this question would it not make sense that a person would need to see a minimal representation of the implementation? Post a [mcve] — ryyker, Sep 13 '20 at 15:04
@ryyker but the array is not unsorted, OP is just using a wrong term - instead it is *descending order*. Granted, the duplicate isn't necessarily a correct one here, but, until OP proves otherwise let's assume that it is. — Antti Haapala -- Слава Україні, Sep 13 '20 at 15:14
@AnttiHaapala Thank you for your comment. I'm sorry. I was confused about using the term. And I read the duplicate about branch prediction. I think in case of ascending array, the if-statement always false. About descending one, this always true. So in selection sort, I think this have nothing to do. Is there something I must know about this question? — Guk, Sep 13 '20 at 15:52
@Geum if you'd make this into a fullblown program, including making the test arrays, then it would actually be a *good question*. — Antti Haapala -- Слава Україні, Sep 13 '20 at 16:11
I did it with GCC and I can see the same difference, @ryyker the most amazing thing is that the descending array writes to memory *way more*, but it is still faster :? — Antti Haapala -- Слава Україні, Sep 13 '20 at 16:30
And this with unoptimized. With optimized, the sorted was faster... I still cannot quite explain :'D — Antti Haapala -- Слава Україні, Sep 13 '20 at 16:32
@AnttiHaapala I added the main function. And I knew that if we use "volatile" int i, j, indexMin, temp in binary search function, a asceding array is faster than descending one. — Guk, Sep 13 '20 at 16:33
I get 2680713 A, 2576229 D, 2695650 A, 2632687 D, even though descending does write the new index to *memory* every time :D — Antti Haapala -- Слава Україні, Sep 13 '20 at 16:33
@Antti - your assertion that editing the code into the question in would make it a _good_ question is true. Maybe even worth an up-click. (If you haven't already done so.) — ryyker, Sep 13 '20 at 17:35
There is a cache effect. When descending, the target cell has a higher chance of beeing present in the cache. The ascending walk has a similar cache trashing effect, but the target cell has a higher chance of **not** being cached. — wildplasser, Sep 13 '20 at 18:11
@wildplasser hmm, not sure if it alone will cause the 4 percent difference that I am seeing, though. — Antti Haapala -- Слава Україні, Sep 14 '20 at 07:21

score 3 · Accepted Answer · answered Sep 13 '20 at 16:55

Here goes my 0.02 €.

I could see a 4 % speed difference favouring the descending array over ascending array in unoptimized code on GCC. My hypothesis is that it is caused by the

if (list[j] < list[indexMin]) {
    indexMin = j;
}

being compiled to

        ...
        jge     .L4
        mov     eax, DWORD PTR [rbp-8]
        mov     DWORD PTR [rbp-12], eax
.L4:
        add     DWORD PTR [rbp-8], 1

i.e. it is not a branch prediction failure - for the ascending case the jge always branches, and for the descending case it never branches. The jge taking the branch does take more cycles than actually updating the index variable in cache.

Of course, if you compile with optimization enabled, the ascending code wins.

In selection sort, descending array's performance is faster than ascending array. why?

1 Answers1