Separating the even and odd numbers in an array in C I wrote a working program in C that takes an array with size 2ⁿ, and separates all the even numbers from the odd numbers.
For example: Input: {1,2,3,4,5,6,7,8}, Output: {8,2,6,4,5,3,7,1}
I want my program to be as efficient as possible and to have space complexity O(log n) and time complexity of O(n log n).
This is the code in C:
#include &lt;stdio.h&gt;

void swap(int*, int*);
void arrange(int arr[], int n);

int main() {
    int arr[] = {1,2,3,4,5,6,7,8};
    int size = sizeof(arr)/sizeof(arr[0]);
    arrange(arr,size);
    
    return 0;
}

void arrange(int arr[], int n) {
    
    if (n==1) return;
    
    int istart = 0, iend = n-1;
    while (istart &lt;= iend) {
    if (arr[istart] % 2 == 0) {
        istart++;
        return arrange(arr+istart,n-1);
    }
    else if (arr[iend] % 2 == 1) {
        iend--;
        return arrange(arr,n-1);
    }
    else {
        swap(&amp;arr[istart++],&amp;arr[iend--]);
        return arrange(arr+istart,n-1);
    }
    }
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

How can I improve my code? Maybe make it run faster with a better complexity?
Efficiency
Your code is already more efficient than you think. It has time complexity \$\mathcal{O}(n)\$, and thanks to tail recursion, it also has space complexity \$\mathcal{O}(1)\$.
Avoid forward declarations
I recommend that you avoid the need to forward-declare arrange() and swap() by reversing the order in which the functions appear in your source file. This avoids repeating yourself.
Don't return a void
Unfortunately, the C standard explicitly forbids calling return with an expression in a function returning void, even if the result of that expression itself is also void. While both GCC and Clang allow it, they will produce a warning when the -pedantic option is used. Just separate the call to arrange() from calling the return statement.
Simplify the code
Without making any changes to the algorithm, you can simplify the code. For example, the while-statement is redundant, since its condition will always be true in the first iteration, and you always call return inside the body, so it won't ever repeat. Furthermore, you can avoid having to declare the variables istart and iend. Here is how it could look:
void arrange(int arr[], int n) {
    if (n &lt;= 1)
       return;

    if (arr[0] % 2 == 0) {
        arrange(arr + 1, n - 1);
    } else if (arr[n - 1] % 2 != 0) {
        arrange(arr, n - 1);
    } else {
        swap(&amp;arr[0], &amp;arr[n - 1]);
        arrange(arr + 1, n - 2);
    }
}