###### Asked in Computer Programming

Computer Programming

# What is the pseudocode for merge sort?

## Answer

###### Wiki User

###### April 26, 2015 9:24PM

The pseudocode for merge sort is:

MERGE (*A*, *p*, *q*, *r* )

1. *n*1 ← *q* − *p* + 1 2. *n*2 ← *r* −
*q*

3. Create arrays L[1 . . *n*1 + 1] and R[1 . . *n*2 +
1]

4. **FOR** *i* ← 1 **TO** *n*1

5. **DO** L[*i*] ← A[*p* + *i* − 1]

6. **FOR** *j* ← 1 **TO** *n*2

7. **DO** R[*j*] ← A[*q* + *j* ]

8. L[*n*1 + 1] ← ∞

9. R[*n*2 + 1] ← ∞

10. *i* ← 1

11. *j* ← 1

12. **FOR** *k* ← *p* **TO** *r*

13. **DO IF** L[*i* ] ≤ R[ *j*]

14. **THEN** A[*k*] ← L[*i*]

15. *i* ← *i* + 1

16. **ELSE** A[k] ← R[j]

17. *j* ← *j* + 1

## Related Questions

###### Asked in Science, C Programming

### Examples for internal sorting and external sorting?

External sorting: - Merge sort - Two way merge sort. Internal
sorting: - Heap sort - Bubble sort - Tree sort - quick sort - shell
sort - Insertion sort External sorting: - Merge sort - Two way
merge sort. Internal sorting: - Heap sort - Bubble sort - Tree sort
- quick sort - shell sort - Insertion sort

###### Asked in Science

### What are the advantages and disadvantages of merge sort?

The advantages to merge sort is it is always fast. Even in its
worst case its runtime is O(nlogn). It is also stable.
Disadvantages of Merge sort are that it is not in place so merge
sort uses a lot of memory. It uses extra space proportional to n.
This can slow it down when attempting to sort very large data.

###### Asked in Java Programming, C Programming, .NET Programming

### What are the merits and demerits of merge sort and quick sort?

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.
see related links.

###### Asked in PHP Programming

### How do you merge and sort an array using PHP?

To merge and sort an array in PHP you need to use the
array_merge() and sort() functions like shown in the example
below:
<?php
$array1 = array(1, 5, 3, 9, 7);
$array2 = array(8, 2, 6, 4, 0);
// merge the arrays
$merge = array_merge($array1, $array2); // 1, 5, 3, 9, 7, 8, 2,
6, 4, 0
// sort the array
sort($merge); // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
?>

###### Asked in Computer Programming, Java Programming, C Programming

### Between merge sort quick sort and bubble sort which is the best?

Among those three, you can automatically discard bubble sort as
the worst in general cases (it actually performs quite well when
the list of numbers are already in order, unlike quick sort).
In general, merge sort is O(n log n) and quick sort is O(n log
n). The two main differences are that 1) quick sort can have a
degradation in performance if the pivot point is chosen poorly
(O(n2)), 2) quick sort does not require the extra storage that
merge sort does.
While I'm not an algorithms expert, I do know that most people
tend to err on the side of using quick sort. I have never actually
seen anyone implement a merge sort when they had a choice.