Merge Sort does not work properly. The numbers in array are not sorted

The following is my code for Merge Sort in JAVA, but the output is not expected.

given input is [49, 1, 3, 200, 2, 4, 70, 5]

The output is :

Merge sort : [2, 4, 49, 1, 3, 70, 5, 200]

Which the number is not sorted. I believe the problem is in the merge method. Can anyone help?

merge_sort method:

private static int[] merge_sort(int[] unsorted_array) {
		
		if (unsorted_array.length < 2) {
			return unsorted_array;
		}
		
		int mid = unsorted_array.length / 2;
		
		int[] first_array = new int[mid];
		int[] second_array = new int[unsorted_array.length - mid];
		
		//Copy element to first and second array.
		for (int i = 0; i < mid; i ++) {
			
			first_array[i] = unsorted_array[i];
		}
		
		for (int i = 0; i < second_array.length; i++) {
			
			second_array[i] = unsorted_array[mid + i];
		}
		
		merge_sort(first_array);
		merge_sort(second_array);
		
		int[] sorted_array = merge(first_array, second_array);
		
		return sorted_array;
	}

merge method:

private static int[] merge(int[] first_array, int[] second_array) {
		int[] result = new int[first_array.length + second_array.length];
		
		int index_result = 0;
		int index_first = 0;
		int index_second = 0;
		
		while (index_first < first_array.length && index_second < second_array.length) {
			
			if (first_array[index_first] < second_array[index_second]) {
				
				result[index_result] = first_array[index_first];
				index_first++;		
			} else {
				
				result[index_result] = second_array[index_second];
				index_second++;
			}
			
			index_result++;
		}
		
		while (index_first < first_array.length) {
			
			result[index_result] = first_array[index_first];
			index_result++;
			index_first++;
		}
		
		while (index_second < second_array.length) {
			
			result[index_result] = second_array[index_second];
			index_result++;
			index_second++;
		}
		
		return result;
	}

You are not using the sorted intermediate results to merge, instead using the original splitted arrays. Modify your code as below:

first_array = merge_sort(first_array);
second_array = merge_sort(second_array);
        
int[] sorted_array = merge(first_array, second_array);

Also you don't need to create these intermediate arrays. You just have to pass the low, high pointers to your array to indicate the portions of the array you are sorting and merging.

Like :

private static void merge_sort(int[] unsorted_array, int low, int high) {
        
   if (low == high) return;
                    
   int mid = low + ( high - low ) / 2;
        
   merge_sort(unsorted_array, low, mid);
   merge_sort(unsorted_array, mid+1, high);
        
   merge(unsorted_array, low, mid, high);

}

where high is inclusive and you call this like : merge_sort(arr, 0, arr.length-1)

You've made a very simple mistake.

Those two following lines are wrong in your code:

merge_sort(first_array);
merge_sort(second_array);

You should write those two lines as follows:

first_array = merge_sort(first_array);
second_array = merge_sort(second_array);

cause, your merge_sort() method returns a sorted array. It does not sort in place the unsorted_array parameter. Rather, it returns the sorted elements in a newly created sorted_array. So, you would get the sorted result from return value of merge_sort() method and then, you should merge them. Rather than doing that, you were just merging two unsorted arrays.

Its not necessary, but you could write as follows for clarification:

int[] sorted_first_array = merge_sort(first_array);
int[] sorted_second_array = merge_sort(second_array);
// and then merge
int[] sorted_array = merge(sorted_first_array, sorted_second_array);
// then return
return sorted_array;

[P.S.]: When you are coding in java, please use java variable and method naming convention. Its easier to read code when you're following convention.