Recursively sort a array

I recently came across a simple telephonic interview problem. The problem was to sort an array recursively. But even numbers need to be placed before odd numbers. At first glance it was obvious that it was a simple case of implementation of merge sort.

Create an array that needs to be sorted

Merge sort

If you are unfamiliary with merge sort, we just break the array into sub parts and later combine them based on our criteria. Here, we will maintiain left and right pointer which keeps track of the end of the array. Initially, the left is equal to 0 and right equals to the last element of the array.

We calculate a mid point and recursively call the method twice one half of array and another half of array. lastly we add the crux of our logic in merge sort.

As per our requirement we need to sort even arrays before odd arrays, so we need to have a method to check that.

Lastly we need to write our merge method.

What is the complexity of the program

It's a recursive algorithm , so we need a recurrence