A merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort.

In computer science, merge sort or mergesort is an comparison-based sorting algorithm. It is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945. Image File history File links Merge_sort_algorithm_diagram. ... Image File history File links Merge_sort_algorithm_diagram. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... For other persons named John Neumann, see John Neumann (disambiguation). ... Year 1945 (MCMXLV) was a common year starting on Monday (link will display the full calendar). ...

Algorithm

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
3. Merge the two sublists back into one sorted list.

Mergesort incorporates two main ideas to improve its runtime: This article is about the concept of recursion. ... Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. ...

1. A small list will take fewer steps to sort than a large list.
2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted (see the merge function below for an example implementation).

Example: Using mergesort to sort a list of integers contained in an array: Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. ... For the microarray in genetics, see SNP array. ...

Suppose we have an array A with indices ranging from A’first to A’Last. We apply mergesort to A(A’first..A’centre) and A(centre+1..A’Last) - where centre is the integer part of (A’first + A’Last)/2. When the two halves are returned they will have been sorted. They can now be merged together to form a sorted array.

In a simple pseudocode form, the algorithm could look something like this: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else var middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = mergesort(left) right = mergesort(right) result = merge(left, right) return result 

There are several variants for the merge() function, the simplest variant could look like this:

 function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result 

C implementation

Here is a recursive implementation of an in-place merge sort in C.

 #include <stdlib.h> #include <stdio.h> #include <time.h> // time() for random seed #define MAX 10 void PrintAr(const int *ar, int nSize) { register int i; for(i = 0; i < nSize; i ++) printf("%d ", ar[i]); printf("n"); } void FillRand(int *ar, int nSize) // Fills an array of size nSize with random numbers { register int i; srand(time(NULL)); // Random seed with current time for(i = 0; i < nSize; i ++) ar[i] = rand() % 100; // All generated random numbers won't exceed 99 } void ShiftTo(int *ar, int iDest, int iSrc) //this method is highly innefective, and can't be used for big arrays { register int i = iSrc; int StoreSrc = ar[iSrc]; for(; i > iDest; i --) ar[i] = ar[i - 1]; // Shifts numbers from iDest to iSrc one step forward ar[iDest] = StoreSrc; // Puts final element in the right place } void CombineAr(int *ar, const int left, const int right, const int pivot) { register int i = left, j = pivot + 1; while (j != right + 1 && i != j) // continue until either list runs out  { if(ar[j] <= ar[i]) // Move the jth element in front of the ith element ShiftTo(ar, i ++ , j ++); // ShiftTo(array, destination index, source index) else i ++; // Skip to the next element } } void MergeS(int *ar, int left, int right, int pivot) { if(left == right) return; else { MergeS(ar, left, pivot, (left + pivot) / 2); // First half MergeS(ar, pivot + 1, right, (pivot + right + 1) / 2); // Second half } CombineAr(ar, left, right, pivot); // Combines two sorted arrays (left -> pivot) and (pivot+1 -> right) } int main(void) { int ar[MAX]; FillRand(ar, MAX); // Fills array with random numbers printf("Original array:t"); PrintAr(ar, MAX); MergeS(ar, 0, MAX - 1, MAX / 2); // Call to merge sort the array printf("Sorted array:t"); PrintAr(ar, MAX); return 0; } 

C++ implementation

Here is a templated implementation of the merge sort from Introduction to Algorithms, 2nd edition:

 #include <cstddef> #include <vector> template <typename T> void MERGE(std::vector<T>& A,size_t p,size_t q,size_t r) { size_t i=0; size_t j=0; size_t n1 = q-p+1; size_t n2 = r-q; size_t k = p; std::vector<T> L(n1),R(n2); while (i < n1) { L[i] = A[p+i]; ++i; } while (j < n2) { R[j] = A[q+j+1]; ++j; } i = j = 0; while (i < n1 && j < n2) { if (L[i] < R[j]) { A[k++] = L[i++]; } else { A[k++] = R[j++]; } } while (i < n1) A[k++] = L[i++]; while (j < n2) A[k++] = R[j++]; } template <typename T> void MERGE-SORT(std::vector<T>& A,size_t p,size_t r) { if (p < r) { size_t q = p+((r-p)/2); MERGE-SORT(A,p,q); MERGE-SORT(A,q+1,r); MERGE(A,p,q,r); } } 

Haskell

Here is an implementation of merge sort written in Haskell. Haskell is a functional programming language, and so the merge sort implementation looks quite different to that of C/C++. Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...

 sort :: [a] -> [a] sort [] = [] sort [x] = [x] sort xs = merge (sort xs1) (sort xs2) where (xs1,xs2) = split xs split :: [a] -> ([a],[a]) split xs = splitrec xs xs [] splitrec :: [a] -> [a] -> [a] -> ([a],[a]) splitrec [] ys zs = (reverse zs, ys) splitrec [x] ys zs = (reverse zs, ys) splitrec (x1:x2:xs) (y:ys) zs = splitrec xs ys (y:zs) merge :: [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) = case pred x y of True -> x : merge xs (y:ys) False -> y : merge (x:xs) ys 

Analysis

In sorting n items, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem. Image File history File links No higher resolution available. ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. ...

In the worst case, merge sort does approximately^[1] (n ⌈lg n⌉ - 2^⌈lg n⌉ + 1) comparisons, which is between (n lg n - n + 1) and (n lg n + n + O(lg n)). ^[2] Plot of log2 x In mathematics, the binary logarithm (log2 n) is the logarithm for base 2. ...

For large n and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches α·n fewer than the worst case where .

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case. Q sort redirects here. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...

Recursive implementations of merge sort make 2n - 1 method calls in the worst case, compared to quicksort's n, thus has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive, implementations of merge sort, avoiding method call overhead, are not difficult to code. Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in. Sorting in-place is possible but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time.^[3] In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. A run of the heapsort algorithm sorting an array of randomly permuted values. ...

Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly. ^{[citation needed]} Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

As can be seen from the procedure MergeSort, there are some complaints. One complaint we might raise is its use of 2n locations; the additional n locations were needed because one couldn't reasonably merge two sorted sets in place. But despite the use of this space the algorithm must still work hard, copying the result placed into Result list back into m list on each call of merge . An alternative to this copying is to associate a new field of information with each key. (the elements in m are called keys). This field will be used to link the keys and any associated information together in a sorted list (keys and related informations are called records). Then the merging of the sorted lists proceeds by changing the link values and no records need to moved at all. A field which contains only a link will generally be smaller than an entire record so less space will also be used.

Merge sorting tape drives

Merge sort is so inherently sequential that it's practical to run it using slow tape drives as input and output devices. It requires very little memory, and the memory required does not change with the number of data elements. If you have four tape drives, it works as follows:

1. Divide the data to be sorted in half and put half on each of two tapes
2. Merge individual pairs of records from the two tapes; write two-record chunks alternately to each of the two output tapes
3. Merge the two-record chunks from the two output tapes into four-record chunks; write these alternately to the original two input tapes
4. Merge the four-record chunks into eight-record chunks; write these alternately to the original two output tapes
5. Repeat until you have one chunk containing all the data, sorted --- that is, for log n passes, where n is the number of records.

For the same reason it is also very useful for sorting data on disk that is too large to fit entirely into primary memory. On tape drives that can run both backwards and forwards, you can run merge passes in both directions, avoiding rewind time. Disk storage is a general category of a computer storage mechanisms, in which data is recorded on planar, round and rotating surfaces (disks, discs, or platters). ... Primary storage, or internal memory, is computer memory that is accessible to the central processing unit of a computer without the use of computers input/output channels. ...

Optimizing merge sort

This might seem to be of historical interest only, but on modern computers, locality of reference is of paramount importance in software optimization, because multi-level memory hierarchies are used. In some sense, main RAM can be seen as a fast tape drive, level 3 cache memory as a slightly faster one, level 2 cache memory as faster still, and so on. In some circumstances, cache reloading might impose unacceptable overhead and a carefully crafted merge sort might result in a significant improvement in running time. This opportunity might change if fast memory becomes very cheap again, or if exotic architectures like the Tera MTA become commonplace. It has been suggested that this article or section be merged with Memory locality. ... In computing, optimization is the process of modifying a system to improve its efficiency. ... The hierarchical arrangement of storage in current computer architectures is called the memory hierarchy. ...

Designing a merge sort to perform optimally often requires adjustment to available hardware, eg. number of tape drives, or size and speed of the relevant cache memory levels.

M.A. Kronrod suggested in 1969 an alternative version of merge sort that used constant additional space.

Typical implementation bugs

A typical mistake made in many merge sort implementations is the division of index-based lists in two sublists. Many implementations determine the middle index as outlined in the following implementation example:

 function merge(int left, int right) { if (left < right) { int middle = (left + right) / 2; [...] 

While this algorithm appears to work very well in most scenarios, it fails for very large lists. The addition of "left" and "right" would lead to an integer overflow, resulting in a completely wrong division of the list. This problem can be solved by increasing the data type size used for the addition, or by altering the algorithm:

 int middle = left + ((right - left) / 2); 

Probably faster, and arguably as clear is:

 int middle = (left + right) >>> 1; 

In C and C++ (where you don't have the >>> operator), you can do this:

 middle = ((unsigned) (left + right)) >> 1; 

See more information here: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Comparison with other sort algorithms

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n), and is often faster in practical implementations. Quicksort, however, is considered by many to be the fastest general-purpose sort algorithm. On the plus side, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. A run of the heapsort algorithm sorting an array of randomly permuted values. ... Q sort redirects here. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ...

As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use mergesort^{[dubious – discuss]} or a tuned quicksort depending on the datatypes and for implementation efficiency switch^{[citation needed]} to insertion sort when fewer than seven array elements are being sorted. Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ... The Java platform is the name for a bundle of related programs, or platform, from Sun Microsystems which allow for developing and running programs written in the Java programming language. ... Example of insertion sort sorting a list of random numbers. ...

Utility in online sorting

Mergesort's merge operation is useful in online sorting, where the list to be sorted is received a piece at a time, instead of all at the beginning (see online algorithm). In this application, we sort each new piece that is received using any sorting algorithm, and then merge it into our sorted list so far using the merge operation. However, this approach can be expensive in time and space if the received pieces are small compared to the sorted list — a better approach in this case is to store the list in a self-balancing binary search tree and add elements to it as they are received. In computer science, an online algorithm is one that can process its input piece-by-piece, without having the entire input available from the start. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ...

References

Citations and notes

1. ^ Due to the nature of implementation in computer programming, an exact approximation is a poor idea to display, and could be very misleading to less informed readers. Depending on what language the algorithm is implemented in, what the implementation actually is, and the fact that a perfect implementation of any given algorithm is nearly impossible to attain, then the writer here needs to give at least a percent error , although the data above should be removed entirely. There is a reason for Big-O and Theta notation. Thus the change in wording from "exactly" to "approximately"
2. ^ The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal
3. ^ Jyrki Katajainen. Practical In-Place Mergesort. Nordic Journal of Computing. 1996.

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Cover of books The Art of Computer Programming is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...

General

• Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging", The Art of Computer Programming. Addison-Wesley, 158-168. ISBN 0-201-89685-0. 
• Cormen, Thomas H.; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 2.3: Designing algorithms", Introduction to Algorithms. MIT Press and McGraw-Hill, 27-37. ISBN 0-262-03293-7. 

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

Wikibooks Algorithm implementation has a page on the topic of

Merge sort

• Analyze Merge Sort in an online Javascript IDE
• Mergesort Java Applet
• Mergesort applet with "level-order" recursive calls to help improve algorithm analysis
• Dictionary of Algorithms and Data Structures: Merge sort
• Literate implementations of merge sort in various languages on LiteratePrograms
• Implementation for C++