Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.LinkedList;
- import java.util.Queue;
- public class MergeSort_Algo_iterative {
- public static void main(String[] args)
- {
- // int[] ary = new int[]{20, 9, 3, 10, 300, 201, 11, 100, 77};
- int[] ary = new int[]{20, 9, 3, 10, 88};
- int[] result = mergesort(ary);
- printarray(result);
- }
- private static int[] mergesort(int[] ary) {
- Queue<int[]> myqueue = new LinkedList();
- for (int i = 0; i < ary.length; i++) {
- myqueue.add(new int[]{ary[i]});
- }
- while(myqueue.size()>1){
- int[] aryLeft = myqueue.remove();
- int[] aryRight = myqueue.remove();
- System.out.printf("aryLeft size: %d - aryRight size: %d %n", aryLeft.length, aryRight.length);
- int[] combinedAry = merge(aryLeft, aryRight);
- myqueue.add(combinedAry);
- }
- return myqueue.remove();
- }
- // imagine you are at the last step of mergesort when you are coming from the bottom up.
- // therefore, the array with size 1 is sorted; then up and the arrays with size 2 will be sorted too.
- // here, we are simulating a up-k layers, and now we have two sorted sub-arrays to be merged.
- private static int[] merge(int[] aryleftsorted, int[] aryrightsorted){
- if (aryleftsorted.length == 0) return aryrightsorted;
- if (aryrightsorted.length == 0) return aryleftsorted;
- int[] result = null;
- if (aryleftsorted[0] <= aryrightsorted[0]) { // if smaller, extract it out in this layer
- result = concat(subarray(aryleftsorted, 0, 1) , merge(subarray(aryleftsorted, 1, aryleftsorted.length), aryrightsorted)) ;
- }else {
- result = concat(subarray(aryrightsorted, 0, 1) , merge(aryleftsorted, subarray(aryrightsorted, 1, aryrightsorted.length))) ;
- }
- return result;
- }
- ///// util only below /////
- private static int[] concat(int[] first, int[] second){
- int[] both = Arrays.copyOf(first, first.length + second.length);
- System.arraycopy(second, 0, both, first.length, second.length);
- return both;
- }
- private static int[] copyarray(int[] array){
- return subarray(array, 0, array.length);
- }
- public static int[] subarray(int[] array, int beg, int end) {
- return Arrays.copyOfRange(array, beg, end);
- }
- private static void printarray(int[] ary){
- for (int i = 0; i < ary.length; i++) {
- System.out.printf("%4d" , ary[i]);
- }
- System.out.println();
- }
- private static void print2darray(int[][] ary){
- for (int i = 0; i < ary.length; i++) {
- for (int j = 0; j < ary[i].length; j++) {
- System.out.printf("%4d" , ary[i][j]);
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement