Complexity of function with array having even and odds numbers separate

Question

So i have an array which has even and odds numbers in it. I have to sort it with odd numbers first and then even numbers. Here is my approach to it:

 int key,val;
int odd = 0;
int index = 0;

for(int i=0;i<max;i++)
{
    if(arr[i]%2!=0)
    {
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
        index++;
        odd++;
    }
}

First I separate even and odd numbers then I apply sorting to it. For sorting I have this code:

for (int i=1; i<max;i++)
{
    key=arr[i];
    
    if(i<odd)
    {
       val = 0;
    }
    if(i>=odd)
    {
        val = odd;
    }
    
    for(int j=i; j>val && key < arr[j-1]; j--)
    {
        arr[j] = arr[j-1];
        arr[j-1] = key;
    }
}

The problem i am facing is this i cant find the complexity of the above sorting code. Like insertion sort is applied to first odd numbers. When they are done I skip that part and start sorting the even numbers. Here is my approach for sorting if i have sorted array e.g: 3 5 7 9 2 6 10 12 complexity table

How all this works? in first for loop i traverse through the loop and put all the odd numbers before the even numbers. But since it doesnt sort them. in next for loop which has insertion sort. I basically did is only like sorted only odd numbers first in array using if statement. Then when i == odd the nested for loop then doesnt go through all the odd numbers instead it only counts the even numbers and then sorts them.

Answer 1

I'm assuming you know the complexity of your partitioning (let's say A) and sorting algorithms (let's call this one B).

You first partition your n element array, then sort m element, and finally sort n - m elements. So the total complexity would be:

A(n) + B(m) + B(n - m)

Depending on what A and B actually are you should probably be able to simplify that further.

Edit: Btw, unless the goal of your code is to try and implement partitioning/sorting algorithms, I believe this is much clearer:

#include <algorithm>
#include <iterator>

template <class T>
void partition_and_sort (T & values) {
  auto isOdd = [](auto const & e) { return e % 2 == 1; };
  auto middle = std::partition(std::begin(values), std::end(values), isOdd);
  std::sort(std::begin(values), middle);
  std::sort(middle, std::end(values));
}

Complexity in this case is O(n) + 2 * O(n * log(n)) = O(n * log(n)).

Edit 2: I wrongly assumed std::partition keeps the relative order of elements. That's not the case. Fixed the code example.