Show Menu

Merge Sort Cheat Sheet (DRAFT) by

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


Best used for merging 2 or more sorted data lists - arrays, arraylists or linked­Lists.

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.


public class MergeSort {
    static int[] n = {5, 2, 4, 3, 1, 8, 7, 6};
    private static void sort(int[] n) {
        if (n.length <= 1)
        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);



    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++] = right[index_right++];

        System.arraycopy(left,index_left,n,index_n, left.length-index_left);



public class MergeSortArrayList {
    static ArrayList<Integer> list = new ArrayList(Arrays.asList(5,3,4,1,2,8,7,9,11,9,12));

    private static void sort(ArrayList<Integer> list){
        if(list.size()==1) return;
        ArrayList<Integer> left = new ArrayList<>(list.size()/2);
        ArrayList<Integer> right = new ArrayList<>(list.size()-left.size());

        int mid = list.size()/2;

        for(int i=0;i<mid;i++)
        for(int i=mid;i< list.size();i++)


     private static void merge(ArrayList<Integer> list,ArrayList<Integer> left, ArrayList<Integer> 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){

        for(int i=index_left;i<left.size();i++)

        for(int i=index_right;i<right.size();i++)


 private static Node sort(Node head) {
      if(head==null || return head;
      Node slow=head,fast=head;
      while(!=null &&!=null){
      Node mid = slow;
      Node midNext =;;

      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;
            return right;
            return left;
      if( <={
          result = left;


        return result;