We have an array that is even placed sorted and oddly placed sorted, meaning that the sub-array with even indexes is sorted and the sub-array with odd indexes is sorted.

for example - {1,4,2,7,4,18,5,19,20} the two sorted subarray are {1,2,4,5,20} and {4,7,18,19} - one group with the even indexes and the other with odd indexes.

Is there a way to sort this uniquely sorted array with O(1) space complexity and O(n) time? (meaning to rearrange it to be normally sorted)

CodePudding user response：

No, there is no way you can achieve this in O(n) time and O(1) space, because if that would be possible, you could implement a mergesort, which only uses O(1) space. Just split in odd and even indexes to divide your values in half.

You can read read about why mergesort needs at least O(n) space in this question: Merge sort time and space complexity

CodePudding user response：

I think that the best performance you can get is O(1) - space and O(n log n) - time. This is in-place merge sort.

public final class InPlaceMergeSort {

    public static void sortAsc(int[] arr) {
        sortAsc(arr, 0, arr.length - 1);
    }

    private static void sortAsc(int[] arr, int lo, int hi) {
        if (hi > lo) {
            int mid = lo   (hi - lo) / 2;
            sortAsc(arr, lo, mid);
            sortAsc(arr, mid   1, hi);
            merge(arr, lo, mid, hi);
        }
    }

    private static void merge(int[] arr, int lo, int mid, int hi) {
        if (arr[mid] > arr[mid   1]) {
            for (int i = lo, j = mid, k = mid   1; i <= j && k <= hi; i  ) {
                if (arr[i] > arr[k]) {
                    rotateRight(arr, i, k  );
                    j  ;
                }
            }
        }
    }

    private static void rotateRight(int[] arr, int lo, int hi) {
        int tmp = arr[hi];

        if (hi - lo >= 0)
            System.arraycopy(arr, lo, arr, lo   1, hi - lo);

        arr[lo] = tmp;
    }

}