Skip to content

Instantly share code, notes, and snippets.

@jp26jp
Last active February 22, 2018 20:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jp26jp/cd1ceebcbdb68988dcff33f0094a3e84 to your computer and use it in GitHub Desktop.
Save jp26jp/cd1ceebcbdb68988dcff33f0094a3e84 to your computer and use it in GitHub Desktop.
Merge sort algorithm using an ArrayList
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