# Java greedy algorithm with merge sort source code and proof

• ``````public class Solution {
//Use greedy algorithm. Sort the given array in ascending order and group 2 integers from beginning to end.
//Poof: If there exists any reverse in optimal solution: (ai,bj), (aj, bi) (i<j);
//Then the sum of those two pairs is ai+bi. The orginal is ai+aj, which is bigger than ai+bi (bi<aj). Contradiction.
public int arrayPairSum(int[] nums) {
mergeSort(nums);
int sum = 0;
for(int i = 0; i < nums.length; i=i+2){
sum += nums[i];
}
return sum;
}

public void mergeSort(int[] nums) {
if(nums.length>1){
//merge
int p = nums.length/2;
int[] arr1 = new int[p];
int[] arr2 = new int[nums.length-p];
for (int i = 0; i < p; i++) {
arr1[i] = nums[i];
arr1[i] = nums[i];
}
for (int i = p; i < nums.length; i++) {
arr2[i-p]=nums[i];
arr2[i-p]=nums[i];

}
mergeSort(arr1);
mergeSort(arr2);
//sort
int m = 0,n=0;
for (int i = 0; i < nums.length; i++) {
if (m<arr1.length&&n<arr2.length&&arr1[m]<arr2[n]) {
nums[i]=arr1[m];
nums[i]=arr1[m];
m++;
}
else if (m<arr1.length&&n<arr2.length&&arr1[m]>=arr2[n]) {
nums[i]=arr2[n];
nums[i]=arr2[n];
n++;
}
else if (m>=arr1.length&&n<=arr2.length) {
nums[i]=arr2[n];
nums[i]=arr2[n];
n++;
}
else if (n>=arr2.length&&m<=arr1.length){
nums[i]=arr1[m];
nums[i]=arr1[m];
m++;
}
}
return;
}
else {
return;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.