Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.