Merge sort algorithm, Java, with extra memory
package julio;
import java.util.Arrays;
public class Main
{
public static void main(String[] args) {
MergeSortExtraMemory sorter = new MergeSortExtraMemory();
int[] input1 = {10,4,3,5,1,6,6};
int[] m1 = {2};
int[] m2 = {3};
System.out.println(Arrays.toString(sorter.merge(m1, m2)));
System.out.println(Arrays.toString(input1));
System.out.println(Arrays.toString(sorter.mergeSort(input1)));
}
}
class MergeSortExtraMemory
{
public int[] mergeSort(int[] input)
{
int size = input.length;
if( size < 2) {
return input;
}
int[] left = new int[size/2];
int[] right = new int[size/2 + ((size%2==0)? 0 : 1) ];
for(int i = 0; i < left.length; i++)
left[i] = input[i];
for(int i = 0 ; i < right.length ; i++)
right[i] = input[left.length + i];
return merge(mergeSort(left), mergeSort(right));
}
public int[] merge(int[] input1, int[] input2)
{
int size = input1.length + input2.length;
int[] out = new int[size];
int i1 = 0;
int i2 = 0;
int outIndex = 0;
while (i1 < input1.length && i2 < input2.length) {
if (input1[i1] < input2[i2]){
out[outIndex++] = input1[i1++];
} else {
out[outIndex++] = input2[i2++];
}
}
if (i1 == input1.length) {
while(i2 < input2.length) {
out[outIndex++] = input2[i2++];
}
} else {
while(i1 < input1.length) {
out[outIndex++] = input1[i1++];
}
}
return out;
}
}
import java.util.Arrays;
public class Main
{
public static void main(String[] args) {
MergeSortExtraMemory sorter = new MergeSortExtraMemory();
int[] input1 = {10,4,3,5,1,6,6};
int[] m1 = {2};
int[] m2 = {3};
System.out.println(Arrays.toString(sorter.merge(m1, m2)));
System.out.println(Arrays.toString(input1));
System.out.println(Arrays.toString(sorter.mergeSort(input1)));
}
}
class MergeSortExtraMemory
{
public int[] mergeSort(int[] input)
{
int size = input.length;
if( size < 2) {
return input;
}
int[] left = new int[size/2];
int[] right = new int[size/2 + ((size%2==0)? 0 : 1) ];
for(int i = 0; i < left.length; i++)
left[i] = input[i];
for(int i = 0 ; i < right.length ; i++)
right[i] = input[left.length + i];
return merge(mergeSort(left), mergeSort(right));
}
public int[] merge(int[] input1, int[] input2)
{
int size = input1.length + input2.length;
int[] out = new int[size];
int i1 = 0;
int i2 = 0;
int outIndex = 0;
while (i1 < input1.length && i2 < input2.length) {
if (input1[i1] < input2[i2]){
out[outIndex++] = input1[i1++];
} else {
out[outIndex++] = input2[i2++];
}
}
if (i1 == input1.length) {
while(i2 < input2.length) {
out[outIndex++] = input2[i2++];
}
} else {
while(i1 < input1.length) {
out[outIndex++] = input1[i1++];
}
}
return out;
}
}
<< Home