Is there an efficient implementation of merging in space?
I just coded this working version of mergesort:
static int[] merge(int[] first, int[] second){
int totalsize = first.length + second.length;
int[] merged_array = new int[totalsize];
int i = 0, firstpointer = 0, secondpointer = 0;
while(i < totalsize){
if(firstpointer == first.length){
merged_array[i] = second[secondpointer];
++secondpointer;
}
else if(secondpointer == second.length){
merged_array[i] = first[firstpointer];
++firstpointer;
}
else if(first[firstpointer] < second[secondpointer]){
merged_array[i] = first[firstpointer];
++firstpointer;
}
else{
merged_array[i] = second[secondpointer];
++secondpointer;
}
++i;
}
return merged_array;
}
static int[] mergesort(int[] array){
if(array.length == 1){
return array;
}
else{
int length = array.length;
int[] first = Arrays.copyOfRange(array, 0, (int) length / 2);
int[] second = Arrays.copyOfRange(array, (int) length / 2, length);
return merge(mergesort(first), mergesort(second));
}
}
However, if you noticed, I use the copyOfRange function, which creates a new array that is a copy of a specific portion of the parent array. Is there a merge implementation in java that is more space efficient than this?
+3
source to share
1 answer
Duplicate: How to sort using merge sort algorithm?
Synopsis: Yes, there are memory-related merge types, but they are either a) very complex or b) inefficient in time: O (n ^ 2 log n)
Basically, don't worry. It's not really that much memory you save, and if you really want to, just use quicksort instead.
+2
source to share