an even and odd placed sorted array

Question

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)

... you're only asking for algorithm idea and not the whole code, are you?... — user202729, Jan 19 '22 at 16:26
Given that you already have two sorted sub-arrays then merge sort is the obvious way to go. You just need to keep careful track of your indexes since the two sub-arrays are interleaved. — rossum, Jan 19 '22 at 16:45
Looks like [c++ - Is it possible to do an inplace merge without temporary storage? - Stack Overflow](https://stackoverflow.com/questions/4373307/is-it-possible-to-do-an-inplace-merge-without-temporary-storage?noredirect=1&lq=1) . Although I'm not sure what the complexity of the linked paper in the answer is. — user202729, Jan 19 '22 at 16:50
Does this answer your question? [Is it possible to do an inplace merge without temporary storage?](https://stackoverflow.com/questions/4373307/is-it-possible-to-do-an-inplace-merge-without-temporary-storage) — user202729, Jan 19 '22 at 16:53
Okay, I checked out the paper, it's O(n)/O(1), definitely satisfied. Flag as duplicate. — user202729, Jan 19 '22 at 16:53
Actually, I forgot that the order is a bit different; still, I think you should be able to use something from that. If you can shuffle them to the "normal" order (should be possible) then just use the algorithm. — user202729, Jan 19 '22 at 17:05
@user202729: `O(n)[time]/O(1)[space]` How do you arrive at/Where did you find O(1) space? I see O(√2) - o(n), but not O(1). — greybeard, Jan 20 '22 at 12:25
@greybeard "Wepresent a novel, yet straightfotward **linear-time algorithm** for merging two sorted lists in a **fixed amount of additional space**. " — user202729, Jan 20 '22 at 13:27

Richard Schmidt · Answer 1 · 2022-01-20T08:55:29.930

If you want to achieve this in O(n) time and O(1) space, you're searching for 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 the common implementation of mergesort needs at least O(n) space in this question: Merge sort time and space complexity

Thank to user202729 for giving me a second look on that topic. While your given implementation can reach O(1) space, you dont have a time complexity of O(n log n) anymore, it is O(n²)

But if you repacing the merge part with 2 pointers, climbing both the indexes of the arrays that need to be merged and do a swaping it should be possible to have O(n log n) again

This is not correct, it claims that that particular implementation of merge sort need O(n) space, not that *there's no algorithm*. (in fact it's *already* possible to implement O(1)-memory merge sort, see link above) — user202729, Jan 19 '22 at 16:40

score 0 · Answer 2 · answered Jan 19 '22 at 19:50

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;
    }

}

Nope, this algorithm is even more wrong, a rotate step is course case O(n). See comment https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm?noredirect=1&lq=1#comment11573033_2571114 — user202729, Jan 20 '22 at 08:28

an even and odd placed sorted array

2 Answers2