Show Menu
Cheatography

# Merge Sort Cheat Sheet (DRAFT) by evanescesn09

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Introd­uction

 Best used for merging 2 or more sorted data lists - arrays, arraylists or linked­Lists. Steps: 1. Divide the array/­arr­ayL­ist­/Li­nke­dList into 2 halves 2. Recurs­ively divide the 2 sublists into 2 halves, and so on till each sublist contains only 1 element 3. Start merging the sublists i.e n sublists take n-merges.
Time Comple­xity: O(nlogn)
Space Comple­xity: O(n) because it uses extra buffer to hold the elements during merge.

### Arrays

 ``````public class MergeSort {     static int[] n = {5, 2, 4, 3, 1, 8, 7, 6};     private static void sort(int[] n) {         if (n.length <= 1)             return;         int[] left = new int[n.length/2];         int[] right = new int[n.length-left.length];         /*         public static void arraycopy (Object src, int srcPos, Object dest, int destPos, int length)             src - Source array (Object type)             srcPos - Starting position in Source array (Integer type)             dest - Destination array (Object Type)             destpos - Starting position in destination array (Integer type)             length - Number of elements to be copied (Integer type)          */         System.arraycopy(n, 0, left, 0, left.length);         System.arraycopy(n, left.length, right, 0, right.length);         sort(left);         sort(right);         merge(n,left,right);     }     private static void merge(int[] n,int[] left, int[] right){         int index_left=0, index_n=0,index_right=0;         while(index_left < left.length && index_right < right.length){             if(left[index_left] <= right[index_right]){                 n[index_n++]=left[index_left++];             }             else                 n[index_n++] = right[index_right++];         }         System.arraycopy(left,index_left,n,index_n, left.length-index_left);         System.arraycopy(right,index_right,n,index_n,right.length-index_right);     } }``````

### ArrayList

 ``````public class MergeSortArrayList {     static ArrayList list = new ArrayList(Arrays.asList(5,3,4,1,2,8,7,9,11,9,12));     private static void sort(ArrayList list){         if(list.size()==1) return;         ArrayList left = new ArrayList<>(list.size()/2);         ArrayList right = new ArrayList<>(list.size()-left.size());         int mid = list.size()/2;         for(int i=0;i list,ArrayList left, ArrayList right){         int index=0, index_left=0,index_right=0;         while(index_left < left.size() && index_right < right.size()){             if(left.get(index_left).compareTo(right.get(index_right)) < 0){                 list.set(index,left.get(index_left));                 index_left++;             }             else{                 list.set(index,right.get(index_right));                 index_right++;             }             index++;         }         for(int i=index_left;i

### LinkedList

 `````` private static Node sort(Node head) {       if(head==null || head.next==null) return head;       Node slow=head,fast=head;       while(fast.next!=null && fast.next.next!=null){           slow=slow.next;           fast=fast.next.next;       }       Node mid = slow;       Node midNext = mid.next;       mid.next=null;       Node left=sort(head);       Node right=sort(midNext);       Node result=merge(left,right);       return result;     }     private static Node merge(Node left, Node right){         Node result = null;         if(left==null)             return right;         if(right==null)             return left;       if(left.data <= right.data){           result = left;           result.next=merge(left.next,right);       }       else{           result=right;           result.next=merge(left,right.next);       }         return result;  }``````