PosNegMergeSort.java

import java.util.Arrays;

/**
 * Author: Towdium
 * Date: 22/04/19
 */
public class PosNegMergeSort {
    public static void main(String[] args) {
        int[] is = new int[]{1, 2, 3, -2, -4, 5, 3, -2, 4, 1, -5, 3};
        sort(is);
        System.out.println(Arrays.toString(is));
        // [1, 2, 3, 5, 3, 4, 1, 3, -2, -4, -2, -5]
    }

    public static void sort(int[] is) {
        local(is);
        int l = 2;
        do {
            for (int i = 0; i < (is.length + l - 1) / l  / 2; i++) {
                int j = i * 2 * l;
                merge(is, j, j + l, Math.min(is.length, j + 2 * l));
            }
            l *= 2;
        } while (l < is.length);
    }

    private static void merge(int[] is, int a, int b, int c) {
        int l = search(is, a, b);
        int r = search(is, b, c);
        int ls = b - l;
        int rs = r - b;
        int ts = ls + rs;
        int cnt = kick(is, l, ls, ts);
        for (int i = 1; i < ts / cnt; i++)
            kick(is, l + i, ls, ts);
    }

    private static int kick(int[] is, int begin, int diff, int total) {
        int count = 1;
        int idx = begin;
        int nxt = (idx + diff - begin) % total + begin;
        int tmp = is[idx];
        while (nxt != begin) {
            is[idx] = is[nxt];
            idx = nxt;
            count++;
            nxt = (idx + diff - begin) % total + begin;
        }
        is[idx] = tmp;
        return count;
    }

    private static int search(int[] is, int a, int b) {
        for (int i = a; i < b; i++) {
            if (is[i] < 0) return i;
        }
        return b;
    }

    private static void local(int[] is) {
        for (int i = 0; i < is.length / 2; i++) {
            int j = i * 2;
            if (is[j] < 0 && is[j+1] > 0) {
                int tmp = is[j];
                is[j] = is[j+1];
                is[j+1] = tmp;
            }
        }
    }
}