# Merge sort

50 %
50 %
Technology

Published on March 5, 2014

Author: barkha33

Source: slideshare.net

MERGE SORT PRESENTED BY: SINDHOO OAD

Merge Sort  Merge sort is based on the divide-and-conquer paradigm.  To sort A[p .. r]: 1. Divide Step If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r]. 2. Conquer Step Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r). Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

The following figure tells to continue expanding until the problem sizes get down to 1.

a problem of size n subproblem 1 of size n/2 subproblem 2 of size n/2 a solution to subproblem 1 a solution to subproblem 2 a solution to the original problem

Example 1: 2 3 4 5 6 7 8 5 2 4 7 1 3 2 6 1 q=4 Divide 1 3 4 5 2 1 2 4 7 5 3 4 5 2 4 7 5 7 8 1 3 2 6 2 6 6 7 8 1 3 2 6 1 2 3 4 5 6 7 8 5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8 1 2 2 3 4 5 6 7 Conquer and Merge 1 3 4 2 4 1 2 5 7 5 3 4 2 5 4 7 5 7 8 1 2 2 6 3 6 6 7 8 1 3 2 6 1 2 3 4 5 6 7 8 5 2 4 7 1 3 2 6

Example 2: 99 6 86 15 58 35 86 4 0

99 99 6 6 86 15 58 35 86 86 15 58 35 86 4 0 4 0

99 99 99 6 6 6 86 15 58 35 86 86 15 58 35 86 86 15 58 35 4 0 4 0 86 4 0

99 99 99 99 6 6 6 6 86 15 58 35 86 86 15 58 35 86 86 15 86 15 4 0 4 0 58 35 86 4 58 86 35 0 4 0

99 99 99 99 6 6 6 6 86 15 58 35 86 86 15 58 35 86 86 15 86 15 4 0 4 0 58 35 86 4 58 86 35 0 4 4 0 0

99 Merge 6 86 15 58 35 86 0 4 4 0

6 99 Merge 99 6 15 86 86 15 58 35 0 58 86 35 4 86 0 4

Merge Sort Example 6 6 Merge 99 15 86 99 15 86 0 4 58 35 35 58 86 0 4 86

0 6 Merge 4 6 15 35 58 86 86 99 15 86 99 0 4 35 58 86

Pros:  It is a stable sort, and there is no worst-case scenario.  It is faster, the temp array holds the resulting array until both left and right sides are merged into the temp array, then the temp array is appended over the input array.  It is used in tape drives to sort data - its good with parallel processing.

Cons:  The memory requirement is doubled.  Takes longer to merge because if the next element is in the right side then all of the elements must be moved down.

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### Mergesort – Wikipedia

Mergesort (von englisch merge ‚verschmelzen‘ und sort ‚sortieren‘) ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche ...

### Mergesort - Studiengang Angewandte Informatik

c) Bitonische Variante der Funktion merge. Bei dieser Variante der Funktion merge wird die vordere Hälfte der Folge in ihrer normalen Reihenfolge, die ...

### Javabeginners - Mergesort

sort(q + 1, r); merge(l, q, r); } return intArr; } private void merge(int l, int q, int r) { int[] arr = new int[intArr.length]; int i, j; ...

### Merge Sort - Sorting Algorithm Animations | Toptal

Animation, code, analysis, and discussion of merge sort on 4 initial conditions.

### Merge sort - Wikipedia, the free encyclopedia

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the ...

### Sorting algorithms/Merge sort - Rosetta Code

Sorting algorithms/Merge sort You are encouraged to solve this task according to the task description, using any language you may know.

### Algorithm Implementation/Sorting/Merge sort - Wikibooks ...

Merge Sort . You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at ...

### mergesort.cpp - godx.de

godX.de; Mergesort; mergesort.cpp. // Merge sort // // Simplified code as example for the merge sort algorithm. // // by feyd//godX.de #include # ...