Skip to content

Instantly share code, notes, and snippets.

@warlock2k
Created May 17, 2020 08:10
Show Gist options
  • Save warlock2k/69e374c7e1e0d7369c0e7a5674c4565b to your computer and use it in GitHub Desktop.
Save warlock2k/69e374c7e1e0d7369c0e7a5674c4565b to your computer and use it in GitHub Desktop.
class Solution
{
public int[] sortArray(int[] nums)
{
mergeSort(nums, nums.length);
return nums;
}
public void mergeSort(int[] nums, int length)
{
// That is if the array is one single size return;
// This is the base case.
if(length < 2)
return;
// Divide the length/2 to find mid point.
int mid = length/2;
/* Mid Point:
* For example, if the array is [5, 4, 9, 8, 2]
* length = 5; length/2 would give mid = 2. Mid represents size not index.
* This means, 2 is the size of the left subarray and
* (length - mid) i.e (5 - 2 = 3) is the size of right sub array.
* So, left-subarray = [5, 4]; right-subarray is [9, 8, 2]
*/
// Array for holding the left integers.
int[] left = new int[mid];
// Array for holding the right integers.
int[] right = new int[length - mid];
// In this part we are simple iterating over the main array and creating left and right sub arrays.
for(int i = 0; i < length; i++)
{
if(i < mid)
{
left[i] = nums[i];
}
else
{
right[i - mid] = nums[i];
}
}
/* BEAUTY OF RECURSION
* Now we simply call the same function mergeSort on left subarray and right subarray.
* Left sub array: [5, 4] after the below recursion would become two new sub arrays [5] and [4].
* (Yay we have reached out base case)
* Right sub array: [9, 8, 2] after the below recursion would become [9] and [8, 2].
* [8, 2] will further recurse to form [8] and [2].
*/
mergeSort(left, mid);
mergeSort(right, length - mid);
/* Once we reach base cases we merge by comparing them against each other.
* For example [5] and [4] would me merged into [4, 5]
* [8] and [2] will be merged into [2, 8]
* [4, 5] and [2, 8] will be merged into [2, 4, 5, 8]
*/
merge(nums, left, right, mid, length - mid);
}
/* Merge logic is quite simple
* If you have two arrays say A[4, 5] and B[2, 8] coming from [5, 4, 8, 2]. It is imporant to note than both [4, 5] and
* [2, 8] come sorted as a consequence of the previous merge call to base arrays [5], [4] & [8], [2] separately.
* Now assuming A and B are sorted.
* We will compare this way:
* 1. is 4 < 2, no? so keep 2 in the first index of [4, 5, 2, 8] makingit [2, 5, 2, 8] and increment pointer in B to 8.
* 2. is 4 < 8 yes? so keep 4 in the second index of [2, 5, 2, 8] making it [2, 4, 2, 8] and incrment pointer in A to 5.
* 3. is 5 <8 yes? so keep 5 in third index of [2, 5, 2, 8] making it. [2, 4, 5, 8].
* There you go it is sorted now.
*/
public void merge(int[] nums, int[] left, int[] right, int l, int r)
{
int i = 0; int j = 0; int k = 0;
while(i < l && j < r)
{
if(left[i] <= right[j])
{
nums[k++] = left[i++];
}
else
{
nums[k++] = right[j++];
}
}
while(i < l)
{
nums[k++] = left[i++];
}
while(j < r)
{
nums[k++] = right[j++];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment