Merge sort
works as follows:
1. Divide
the unsorted list into n sublists, each containing 1 element (a list of 1
element is considered sorted).
2. Repeatedly
merge sublists to produce new sorted sublists until there is only 1 sublist
remaining. This will be the sorted list.
Merger Sort
Works in O(nlogn) time in best, average, worst cases.
Following video
explains merge sort clearly.
import java.util.Objects; public class MergeSort<T extends Comparable<T>> { private T arr[]; private boolean isAscending; /** * If flag is true, then elements are sorted in ascending order, else * descending order */ public void sort(T arr[], boolean flag) { Objects.nonNull(arr); this.arr = arr; isAscending = flag; if (flag == true) sortAscending(0, arr.length - 1); else sortDescending(0, arr.length - 1); } private void sortAscending(int left, int right) { int mid = (left + right) / 2; if (left < right) { sortAscending(left, mid); sortAscending(mid + 1, right); merge(left, mid, right); } } private void sortDescending(int left, int right) { int mid = (left + right) / 2; if (left < right) { sortDescending(left, mid); sortDescending(mid + 1, right); merge(left, mid, right); } } /* If falg is true compare for ascending order, else descending order */ private boolean compare(T elem1, T elem2) { return elem1.compareTo(elem2) <= 0; } @SuppressWarnings("unchecked") private void merge(int left, int mid, int right) { int low = left, high = mid + 1, k; Object temp[] = new Object[right - left + 1]; int counter = 0; if (isAscending) while (low <= mid && high <= right) { if (compare(arr[low], arr[high])) temp[counter++] = arr[low++]; else temp[counter++] = arr[high++]; } else { while (low <= mid && high <= right) { if (compare(arr[high], arr[low])) temp[counter++] = arr[low++]; else temp[counter++] = arr[high++]; } } if (low > mid) for (k = high; k <= right; k++) temp[counter++] = arr[k]; else for (k = low; k <= mid; k++) temp[counter++] = arr[k]; counter = 0; for (k = left; k <= right; k++) arr[k] = (T) temp[counter++]; } }
Following is
the junit test case for above program.
import static org.junit.Assert.assertTrue; import java.util.Arrays; import org.junit.Test; public class MergeSortTest { @Test public void test1() { MergeSort<Integer> obj1 = new MergeSort<>(); Integer arr1[] = { 5, 46, 25, 13, 12 }; Integer arr2[] = { 5, 46 }; Integer arr3[] = { 5, 4, 3, 2, 1 }; Integer arr4[] = { 1 }; Integer arr5[] = { 1, 3, 5, 7, 2, 4, 6, 8 }; obj1.sort(arr1, false); obj1.sort(arr2, false); obj1.sort(arr3, false); obj1.sort(arr4, false); obj1.sort(arr5, false); assertTrue(Arrays.equals(arr1, new Integer[] { 46, 25, 13, 12, 5 })); assertTrue(Arrays.equals(arr2, new Integer[] { 46, 5 })); assertTrue(Arrays.equals(arr3, new Integer[] { 5, 4, 3, 2, 1 })); assertTrue(Arrays.equals(arr4, new Integer[] { 1 })); assertTrue(Arrays .equals(arr5, new Integer[] { 8, 7, 6, 5, 4, 3, 2, 1 })); } @Test public void test2() { MergeSort<Integer> obj1 = new MergeSort<>(); Integer arr1[] = { 5, 46, 25, 13, 12 }; Integer arr2[] = { 5, 46 }; Integer arr3[] = { 5, 4, 3, 2, 1 }; Integer arr4[] = { 1 }; Integer arr5[] = { 1, 3, 5, 7, 2, 4, 6, 8 }; obj1.sort(arr1, true); obj1.sort(arr2, true); obj1.sort(arr3, true); obj1.sort(arr4, true); obj1.sort(arr5, true); assertTrue(Arrays.equals(arr1, new Integer[] { 5, 12, 13, 25, 46 })); assertTrue(Arrays.equals(arr2, new Integer[] { 5, 46 })); assertTrue(Arrays.equals(arr3, new Integer[] { 1, 2, 3, 4, 5 })); assertTrue(Arrays.equals(arr4, new Integer[] { 1 })); assertTrue(Arrays .equals(arr5, new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8 })); } }
No comments:
Post a Comment