/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main
(String[] args
) { int[] massif = {5, 2, 4, 6, 1, 3, 2, 6};
System.
out.
print("Массив до сортировки: "); for (int i = 0; i < massif.length; i++)
System.
out.
print(massif
[i
] + " "); massif = Sort(massif);
System.
out.
print("Массив после сортировки: "); for (int i = 0; i < massif.length; i++)
System.
out.
print(massif
[i
] + " "); }
public static int[] Sort(int X[]) {
if (X.length == 1)
return X;
else {
int half
= (int) Math.
floor(X.
length / 2); int halfFirst[] = new int[half];
int halfSecond[] = new int[X.length - half];
for (int i = 0; i < X.length; i++) {
if (i < half)
halfFirst[i] = X[i];
else
halfSecond[i - half] = X[i];
}
halfFirst = Sort(halfFirst);
halfSecond = Sort(halfSecond);
X = SortNext(halfFirst, halfSecond);
return X;
}
}
public static int[] SortNext(int A[], int B[]) {
int C[] = new int [A.length + B.length];
int a = 0, b = 0;
for (int i = 0; i < A.length + B.length; i++) {
if (a == A.length) {
C[i] = B[b];
b++;
}
else if (b == B.length) {
C[i] = A[a];
a++;
}
else if (A[a] > B[b]) {
C[i] = B[b];
b++;
}
else {
C[i] = A[a];
a++;
}
}
return C;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSBtYXNzaWYgPSB7NSwgMiwgNCwgNiwgMSwgMywgMiwgNn07CiAgICAgICAgU3lzdGVtLm91dC5wcmludCgi0JzQsNGB0YHQuNCyINC00L4g0YHQvtGA0YLQuNGA0L7QstC60Lg6ICIpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWFzc2lmLmxlbmd0aDsgaSsrKQogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KG1hc3NpZltpXSArICIgIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCIiKTsKICAgICAgICBtYXNzaWYgPSBTb3J0KG1hc3NpZik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludCgi0JzQsNGB0YHQuNCyINC/0L7RgdC70LUg0YHQvtGA0YLQuNGA0L7QstC60Lg6ICIpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWFzc2lmLmxlbmd0aDsgaSsrKQogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KG1hc3NpZltpXSArICIgIik7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyBpbnRbXSBTb3J0KGludCBYW10pIHsKICAgICAgICBpZiAoWC5sZW5ndGggPT0gMSkKICAgICAgICAgICAgcmV0dXJuIFg7CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIGludCBoYWxmID0gKGludCkgTWF0aC5mbG9vcihYLmxlbmd0aCAvIDIpOwogICAgICAgICAgICBpbnQgaGFsZkZpcnN0W10gPSBuZXcgaW50W2hhbGZdOwogICAgICAgICAgICBpbnQgaGFsZlNlY29uZFtdID0gbmV3IGludFtYLmxlbmd0aCAtIGhhbGZdOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IFgubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgICAgIGlmIChpIDwgaGFsZikKICAgICAgICAgICAgICAgICAgICBoYWxmRmlyc3RbaV0gPSBYW2ldOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGhhbGZTZWNvbmRbaSAtIGhhbGZdID0gWFtpXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBoYWxmRmlyc3QgPSBTb3J0KGhhbGZGaXJzdCk7CiAgICAgICAgICAgIGhhbGZTZWNvbmQgPSBTb3J0KGhhbGZTZWNvbmQpOwogICAgICAgICAgICBYID0gU29ydE5leHQoaGFsZkZpcnN0LCBoYWxmU2Vjb25kKTsKICAgICAgICAgICAgcmV0dXJuIFg7CiAgICAgICAgfQogICAgfQogICAgcHVibGljIHN0YXRpYyBpbnRbXSBTb3J0TmV4dChpbnQgQVtdLCBpbnQgQltdKSB7CiAgICAgICAgaW50IENbXSA9IG5ldyBpbnQgW0EubGVuZ3RoICsgQi5sZW5ndGhdOwogICAgICAgIGludCBhID0gMCwgYiA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBBLmxlbmd0aCArIEIubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgaWYgKGEgPT0gQS5sZW5ndGgpIHsKICAgICAgICAgICAgICAgIENbaV0gPSBCW2JdOwogICAgICAgICAgICAgICAgYisrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYgKGIgPT0gQi5sZW5ndGgpIHsKICAgICAgICAgICAgICAgIENbaV0gPSBBW2FdOwogICAgICAgICAgICAgICAgYSsrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBpZiAoQVthXSA+IEJbYl0pIHsKICAgICAgICAgICAgICAgICAgICBDW2ldID0gQltiXTsKICAgICAgICAgICAgICAgICAgICBiKys7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UgewogICAgICAgICAgICAgICAgQ1tpXSA9IEFbYV07CiAgICAgICAgICAgICAgICBhKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIEM7CiAgICB9Cn0=