This is a code from Introduction to Java Programming about Merge Sort. This method uses a recursion implementation.
public class MergeSort {
2 /** The method for sorting the numbers */
3 public static void mergeSort(int[] list) {
4 if (list.length > 1) {
5 // Merge sort the first half
6 int[] firstHalf = new int[list.length / 2];
7 System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
8 mergeSort(firstHalf);
9
10 // Merge sort the second half
11 int secondHalfLength = list.length - list.length / 2;
12 int[] secondHalf = new int[secondHalfLength];
13 System.arraycopy(list, list.length / 2,
14 secondHalf, 0, secondHalfLength);
15 mergeSort(secondHalf);
16
17 // Merge firstHalf with secondHalf into list
18 merge(firstHalf, secondHalf, list);
19 }
20 }
My question: is in Line 8 calls the recursion method back to "mergeSort"? If running from the beginning of the method, the "firstHalf" array will be created again and the length will be half short. I think the "firstHalf" can not created again and the length should not be changed if an array is defined already.
Here is the whole code link: Merge Sort Java.
This is beginner's way of thinking. Yes, exactly I thought the same when I encountered this before. I couldn't believe that the same array size can change dynamically. Understand this, in the below code, array l and array r are created with different sizes for every recursive call. Don't confuse on this.
Yes, this is never possible that the same array size changes dynamically for a beginner like you and me. But, there is an exception, well, there are exceptions. We will see them very often as we move forward.
Its recursion, in recursion things change dynamically and all this changes are stored in a call stack.
Its confusing but its really interesting if you ponder over it. Its profound. Merge sort can be implemented in quite different ways, but the underlying concept of recursion is same. Don't get confused here, Its better you follow another way to do it, video:
Merge sort first takes a list or an array. Lets imagine the
a.length; #lenght of an array is 8
Now the end goal is to split the array recursively, till it reaches to a point where there are no-elements (only-one). And a single element is always sorted.
See the base case in the below code:
if(a.length<2) /*Remember this is the base case*/
{
return;
}
Once it reaches to single element, sort and merge them back. This way you get a complete sorted array which is easy to merge. The only reason we are doing all this non-sense is to get a better run-time algorithm which is O(nlogn).
Because, all the other sorting algos (insertion, bubble, and selection) will take O(n2), which is alot, too much indeed. So, humanity must figure out the better solution. Its a need for humanity, very important. I know its annoying, I had gone through this non-sense.
Please do some research on recursion before you attempt on this. Understand recursion clearly. Keep all this away. Take a simple recursion example and start working on it. Take a factorial example. Its a bad example but its easy to understand.
See my code, its nice and easy. Again, both are not easy to understand on your first attempt. You must get in touch with recursion before you attempt to understand these things. All the very best.
public class MergeSort
{
private int low;
private int high;
private int mid;
public static int[] a;
public MergeSort(int x)
{
a = new int[x];
a[0]=19;
a[1]=10;
a[2]=0;
a[3]=220;
a[4]=80;
a[5]=2000;
a[6]=56001;
a[7]=2;
}
public void division(int[] a)
{
low=0;
int p;
high = a.length;
mid = (high+low)/2;
if(a.length<2) /*Remember this is the base case*/
{
return;
}
else
{
int[] l = new int[mid];
int[] r = new int[high-mid];
/*copying elements from a into l and r*/
for(p=0;p<mid;p++)
l[p]=a[p];
for(int q=0;q<high-mid;q++, p++)
r[q]=a[p];
/*first recursive call starts from here*/
division(l);
division(r);
sortMerge(a, l, r);
}
}
public void sortMerge(int[] a, int[] l, int[] r)
{
int i=0, j=0, k=0;
/*sorting and then merging recursively*/
while(i<l.length && j<r.length)
{
if(l[i]<r[j])
{
a[k] = l[i]; /*copying sorted elements into a*/
i++;
k++;
}
else
{
a[k] = r[j];
j++;
k++;
}
}
/*copying remaining elements into a*/
while(i<l.length)
{
a[k] = l[i];
i++;
k++;
}
while(j<r.length)
{
a[k] = r[j];
j++;
k++;
}
}
/*method display elements in an array*/
public void display()
{
for(int newIndex=0;newIndex<a.length;newIndex++)
{
System.out.println(a[newIndex]);
}
}
public static void main(String[] args)
{
MergeSort obj = new MergeSort(8);
obj.division(a);
obj.display();
}
}