# Merge Sort with Graphical explanation

One of the most basic and powerful algorithmic techniques is **Divide and Conquer**. For example, the binary search algorithm, which I’ll describe in the context of **guess a number game** between 1 and 100. Suppose someone picks a number between 1 and 100, and allows you to ask questions of the form “Is the number greater than k?” where k is an integer you choose. In this problem, goal is to ask as few questions as possible to figure out the number. Your first question should be “Is the number greater than 50?” Why? Because after asking if the number is bigger than 50, you have learned either that the number is between 1 and 50, or that the number is between 51 and 100. In either case have reduced your problem to one in which the range is only half as big. Thus you have divided the problem up into a problem that is only half as big, and you can now (recursively) conquering this remaining problem.

Merge sort algorithm also uses this divide and conquer strategy to sort an array of elements. Merge sort algorithm performs sorting in two phases. **In first phase**, algorithm splits an array into two equal length sub-arrays. This process recursively continues on the sub-arrays until there is only one element in the sub-array. **In phase two**, merging process takes place that will take two sorted sub-arrays of A and merges them into a single sorted sub-array of A.

MergeSort(A, left, right) { if (left < right) { mid = floor((left + right) / 2); MergeSort(A, left, mid); MergeSort(A, mid+1, right); Merge(A, left, mid, right); } } Merge(A, left, mid, right) { int B[left..right]; int i=k=left; int j = mid+1 while (i <= mid) and (j <= right) if (A[i] <= A[j]) B[k++] = A[i++]; else B[k++] = A[j++]; while (i <= mid) B[k++] = A[i++]; while (j <= right) B[k++] = A[j++]; for (i = left; i <= right; i++) A[i] = B[i]; }

## Graphical Explanation

Consider the following array: **A = {7, 5, 2, 4, 1, 6, 3, 0};**

In first phase, algorithm will split this array into single element sub-arrays.

In second phase, algorithm will combine two sorted sub-arrays in to a single sorted sub-array. Finally, a single sorted array remains that contain the sorted output.

### Related Posts

- Quick Sort Algorithm with Graphical Explanation
- Operations on Binary Search Trees (BST)
- This Pointer, Static Members and destructors in C++
- Recursion in C++
- Introduction to Recursion in C++
- Binary Trees and Binary Search Trees
- Selection Sort: A Graphical Explanation
- Boyer-Moore String Searching Algorithm
- Binary Search Trees and Data Structure
- Heap Sort with Graphical Explanation
- Applications of Dijkstra Algorithm
- Circular Linked Lists

### Popular Posts (last 30 days)

- Attendance Management Sys… 1185 view(s)
- Graph Implementation in C… 587 view(s)
- Implementing Stack Data S… 578 view(s)
- Circular Linked Lists 524 view(s)
- Applications of Stack in … 523 view(s)
- Simple Currency Converter… 442 view(s)
- GRASP Design Patterns 328 view(s)
- Advanced Data Structures … 265 view(s)
- C++ Tutorial for Intermed… 253 view(s)
- Sockets and Network Progr… 185 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books