Last active
February 22, 2018 20:59
-
-
Save jp26jp/cd1ceebcbdb68988dcff33f0094a3e84 to your computer and use it in GitHub Desktop.
Merge sort algorithm using an ArrayList
This file contains hidden or 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
void mergeSort(final ArrayList list, final int start, final int end) | |
{ | |
if (start >= end) | |
return; | |
int middle = (start + end) / 2; | |
mergeSort(list, start, middle); // Sort the left side of the list | |
mergeSort(list, middle + 1, end); // Sort the right side of the list | |
merge(list, new ArrayList<>(list.size()), start, middle + 1, end + 1); // Merge both sides | |
} | |
void merge(ArrayList<Integer> list, ArrayList<Integer> tempList, final int staticLeft, final int staticRight, final int staticEnd) | |
{ | |
int dynamicLeft = staticLeft, dynamicRight = staticRight; | |
while (dynamicLeft < staticRight && dynamicRight < staticEnd) | |
if (list.get(dynamicLeft) <= list.get(dynamicRight)) | |
tempList.add(list.get(dynamicLeft++)); | |
else | |
tempList.add(list.get(dynamicRight++)); | |
while (dynamicLeft < staticRight) tempList.add(list.get(dynamicLeft++)); | |
while (dynamicRight < staticEnd) tempList.add(list.get(dynamicRight++)); | |
int i = staticLeft; | |
for (Integer value : tempList) | |
list.set(i++, value); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment