CODEWITHSUNDEEP
c++algorithmsorting
user1120144
user1120144

Reputation:

What kind of sorting is this and what's its running time?

I was wondering what kind of sorting is the sorting below, and what is its running time in big O notation? My friend wrote this sorting function without any knowledge of algorithms and now we are arguing about how fast/memory efficient it is. So please, can you help us with the analysis.

void sort(int* a, int size)
{
    if (size <= 1) return;
    else if (size == 2)
    {
        if (a[0] > a[1])
            swap (a[0], a[1]);
        return;
    }
    else
    {
        int i = size / 2;
        sort(a, i);
        sort(a+i, size - i);
        int j = 0, k = i ;
        while (k < size && j < k)
        {
            if (a[j] > a[k])
            {
                int temp = k;
                while (temp > j)
                {
                    swap(a[temp - 1], a[temp]);
                    temp--;
                }
                k++;
            }
            j++;
        }
    }
}

Thank you :)

Upvotes: 1

Views: 159

Answers (1)

Dirk Holsopple
Dirk Holsopple

Reputation: 8831

That's basically mergesort, but with a n^2 in-place merge step. If you do the standard math, like you would to analyze mergesort, you should find that it has n^2 running time. The relevant equation you would need to solve to do this is f(n) = n^2 + 2f(n/2).

Upvotes: 2

Related Questions