Merge sort

50 %
50 %
Information about Merge sort
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.

Add a comment

Related presentations

Related pages

Mergesort – Wikipedia

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

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 ...
Read more

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; ...
Read more

Merge Sort - Sorting Algorithm Animations | Toptal

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

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 ...
Read more

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.
Read more

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 ...
Read more

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 # ...
Read more

Sorting algorithms - Studiengang Angewandte Informatik

This variant of function merge requires in each case exactly the same number of steps – no matter if the input sequence is random, sorted or sorted in ...
Read more

Mergesort - hipphampel.de

Die Funktion merge ist der Grund, warum Mergesort insgesamt nicht in situ arbeitet: sie erstellt zunächst zwei Listen u1 und u2 die die zu verschmelzenden ...
Read more