\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{evanescesn09}
\pdfinfo{
  /Title (merge-sort.pdf)
  /Creator (Cheatography)
  /Author (evanescesn09)
  /Subject (Merge Sort Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{11E8F7}
\definecolor{LightBackground}{HTML}{E1FCFE}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Merge Sort Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{evanescesn09} via \textcolor{DarkBackground}{\uline{cheatography.com/88543/cs/20304/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}evanescesn09 \\
  \uline{cheatography.com/evanescesn09} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 18th August, 2019.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{2}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Introduction}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{Best used for merging 2 or more sorted data lists - arrays, arraylists or linkedLists. \newline % Row Count 2 (+ 2)
Steps: \newline % Row Count 3 (+ 1)
1. Divide the \seqsplit{array/arrayList/LinkedList} into 2 halves \newline % Row Count 5 (+ 2)
2. Recursively divide the 2 sublists into 2 halves, and so on till each sublist contains only 1 element \newline % Row Count 8 (+ 3)
3. Start merging the sublists i.e n sublists take n-merges.% Row Count 10 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Time Complexity: O(nlogn) \newline Space Complexity: O(n) because it uses extra buffer to hold the elements during merge.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Arrays}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public class MergeSort \{ \newline     static int{[}{]} n = \{5, 2, 4, 3, 1, 8, 7, 6\}; \newline     private static void sort(int{[}{]} n) \{ \newline         if (n.length \textless{}= 1) \newline             return; \newline         int{[}{]} left = new int{[}n.length/2{]}; \newline         int{[}{]} right = new int{[}n.length-left.length{]}; \newline  \newline         /{\emph{ \newline         public static void arraycopy (Object src, int srcPos, Object dest, int destPos, int length) \newline             src - Source array (Object type) \newline             srcPos - Starting position in Source array (Integer type) \newline             dest - Destination array (Object Type) \newline             destpos - Starting position in destination array (Integer type) \newline             length - Number of elements to be copied (Integer type) \newline          }}/ \newline         System.arraycopy(n, 0, left, 0, left.length); \newline         System.arraycopy(n, left.length, right, 0, right.length); \newline  \newline         sort(left); \newline         sort(right); \newline  \newline         merge(n,left,right); \newline     \} \newline  \newline     private static void merge(int{[}{]} n,int{[}{]} left, int{[}{]} right)\{ \newline         int index\_left=0, index\_n=0,index\_right=0; \newline         while(index\_left \textless{} left.length \&\& index\_right \textless{} right.length)\{ \newline             if(left{[}index\_left{]} \textless{}= right{[}index\_right{]})\{ \newline                 n{[}index\_n++{]}=left{[}index\_left++{]}; \newline             \} \newline             else \newline                 n{[}index\_n++{]} = right{[}index\_right++{]}; \newline         \} \newline  \newline         System.arraycopy(left,index\_left,n,index\_n, \seqsplit{left.length-index\_left);} \newline         System.arraycopy(right,index\_right,n,index\_n,right.length-index\_right); \newline     \} \newline  \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{ArrayList}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public class MergeSortArrayList \{ \newline     static ArrayList\textless{}Integer\textgreater{} list = new \seqsplit{ArrayList(Arrays.asList(5},3,4,1,2,8,7,9,11,9,12)); \newline  \newline     private static void sort(ArrayList\textless{}Integer\textgreater{} list)\{ \newline         if(list.size()==1) return; \newline         ArrayList\textless{}Integer\textgreater{} left = new ArrayList\textless{}\textgreater{}(list.size()/2); \newline         ArrayList\textless{}Integer\textgreater{} right = new ArrayList\textless{}\textgreater{}(list.size()-left.size()); \newline  \newline         int mid = list.size()/2; \newline  \newline         for(int i=0;i\textless{}mid;i++) \newline             left.add(list.get(i)); \newline          \newline         for(int i=mid;i\textless{} list.size();i++) \newline             right.add(list.get(i)); \newline  \newline         sort(left); \newline         sort(right); \newline         merge(list,left,right); \newline     \} \newline  \newline  \newline  \newline      private static void merge(ArrayList\textless{}Integer\textgreater{} list,ArrayList\textless{}Integer\textgreater{} left, ArrayList\textless{}Integer\textgreater{} right)\{ \newline         int index=0, index\_left=0,index\_right=0; \newline         while(index\_left \textless{} left.size() \&\& index\_right \textless{} right.size())\{ \newline             \seqsplit{if(left.get(index\_left).compareTo(right.get(index\_right))} \textless{} 0)\{ \newline                 list.set(index,left.get(index\_left)); \newline                 index\_left++; \newline             \} \newline             else\{ \newline                 list.set(index,right.get(index\_right)); \newline                 index\_right++; \newline             \} \newline             index++; \newline         \} \newline  \newline         for(int i=index\_left;i\textless{}left.size();i++) \newline             list.set(index++,left.get(i)); \newline  \newline         for(int i=index\_right;i\textless{}right.size();i++) \newline             list.set(index++,right.get(i)); \newline     \} \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{LinkedList}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{private static Node sort(Node head) \{ \newline       if(head==null || head.next==null) return head; \newline       Node slow=head,fast=head; \newline       while(fast.next!=null \&\& fast.next.next!=null)\{ \newline           slow=slow.next; \newline           fast=fast.next.next; \newline       \} \newline       Node mid = slow; \newline       Node midNext = mid.next; \newline       mid.next=null; \newline  \newline       Node left=sort(head); \newline       Node right=sort(midNext); \newline  \newline       Node result=merge(left,right); \newline       return result; \newline     \} \newline  \newline     private static Node merge(Node left, Node right)\{ \newline         Node result = null; \newline         if(left==null) \newline             return right; \newline         if(right==null) \newline             return left; \newline       if(left.data \textless{}= right.data)\{ \newline           result = left; \newline           \seqsplit{result.next=merge(left.next},right); \newline       \} \newline  \newline       else\{ \newline           result=right; \newline           result.next=merge(left,right.next); \newline       \} \newline  \newline         return result; \newline  \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}