Analyze the Algorithm below: public class MergeSort { /** The method for sorting
ID: 3530197 • Letter: A
Question
Analyze the Algorithm below:
public class MergeSort {
/** The method for sorting the numbers */
public static void mergeSort(int[] list) {
if (list.length > 1) {
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2,
secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf
int[] temp = merge(firstHalf, secondHalf);
System.arraycopy(temp, 0, list, 0, temp.length);
}
}
/** Merge two sorted lists */
private static int[] merge(int[] list1, int[] list2) {
int[] temp = new int[list1.length + list2.length];
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while (current1 < list1.length && current2 < list2.length) {
if (list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
return temp;
}
/** A test method */
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
Explanation / Answer
I have modified the code a bit to make it compile and work
------------------------------------------------------------------------------
explanation
---------------------------
input : array of integer.
output: sorted array
here you are splitting the array into two and then sorting each of them recursively
to get sorted the array.
merge sort are very useful.
-----------------------------
code
--------------------
public class MergeSort
{
/** The method for sorting the numbers */
public static void mergeSort(int[] list)
{
if (list.length > 1)
{
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf
int[] temp = merge(firstHalf, secondHalf);
System.arraycopy(temp, 0, list, 0, temp.length);
}
}
/** Merge two sorted lists */
static int[] merge(int[] list1, int[] list2)
{
int[] temp = new int[list1.length + list2.length];
int current1 = 0;
// Current index in list1
int current2 = 0;
// Current index in list2
int current3 = 0;
// Current index in temp
while (current1 < list1.length && current2 < list2.length)
{
if (list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
return temp;
}
/** A test method */
public static void main(String[] args)
{
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}