Last active
March 13, 2022 17:18
-
-
Save CollinShoop/7438da59ba45b9dbb1e9f143f6d04aed to your computer and use it in GitHub Desktop.
[Java] Merge sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// in-line recursive merge sort | |
public static void mergeSort(int[] nums) { | |
subMergeSort(nums, 0, nums.length-1, new int[nums.length]); | |
} | |
private static void subMergeSort(int[] nums, int start, int end, int[] swap) { | |
if (start == end) { | |
return; | |
} | |
// sort sub-lists | |
int pivot = (start + end) / 2; | |
// divine and conquer so the left and right lists are sorted | |
if (end - start > 1) { | |
subMergeSort(nums, start, pivot, swap); | |
subMergeSort(nums, pivot + 1, end, swap); | |
} | |
// merge left and right sorted sub lists | |
// results are stored in swap to avoid overwriting | |
int left = start; | |
int right = pivot+1; | |
for (int i = 0; i < end-start+1; i++) { | |
if (left > pivot) { | |
swap[i] = nums[right++]; | |
} else if (right > end) { | |
swap[i] = nums[left++]; | |
} else { | |
// both are in bounds, take the smallest | |
if (nums[left] < nums[right]) { | |
swap[i] = nums[left++]; | |
} else { | |
swap[i] = nums[right++]; | |
} | |
} | |
} | |
// swap back | |
for (int i = 0; i < end - start + 1; i++) { | |
nums[start+i] = swap[i]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment