public class Mergesort {
public static void merge(int[] list, int start, int middle, int end)
{
int[] tmp = new int[list.length];
int ai = start, bi = middle, ti = start;
while (ai < middle || bi < end)
{
if (ai == middle) tmp[ti++] = list[bi++];
else if (bi == end) tmp[ti++] = list[ai++];
else if (list[ai] < list[bi]) tmp[ti++] = list[ai++];
else tmp[ti++] = list[bi++];
}
for (ti = start; ti < end; ti++)
list[ti] = tmp[ti];
}
public static void mergesort(int[] lst, int start, int end)
{
if (end-start < 2)
return;
mergesort(lst, start, start + (end-start) / 2);
mergesort(lst, start + (end-start) / 2, end);
merge(lst, start, start + (end-start) / 2, end);
}
public static void main(String[] args)
{
int[] lst = new int[] {10, 9, 8, 4, 5, 6, 7, 3, 2, 1};
mergesort(lst, 0, lst.length);
for (int i = 0; i < lst.length; i++)
System.out.print(lst[i] + " ");
System.out.println("\n");
}
}
Out put:
1 2 3 4 5 6 7 8 9 10
public static void merge(int[] list, int start, int middle, int end)
{
int[] tmp = new int[list.length];
int ai = start, bi = middle, ti = start;
while (ai < middle || bi < end)
{
if (ai == middle) tmp[ti++] = list[bi++];
else if (bi == end) tmp[ti++] = list[ai++];
else if (list[ai] < list[bi]) tmp[ti++] = list[ai++];
else tmp[ti++] = list[bi++];
}
for (ti = start; ti < end; ti++)
list[ti] = tmp[ti];
}
public static void mergesort(int[] lst, int start, int end)
{
if (end-start < 2)
return;
mergesort(lst, start, start + (end-start) / 2);
mergesort(lst, start + (end-start) / 2, end);
merge(lst, start, start + (end-start) / 2, end);
}
public static void main(String[] args)
{
int[] lst = new int[] {10, 9, 8, 4, 5, 6, 7, 3, 2, 1};
mergesort(lst, 0, lst.length);
for (int i = 0; i < lst.length; i++)
System.out.print(lst[i] + " ");
System.out.println("\n");
}
}
Out put:
1 2 3 4 5 6 7 8 9 10