A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Merge Sort page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

- Jeremy Grifski
- Ron Zuckerman

Merge sort is an algorithm that works by dividing a list into smaller lists. It continues dividing until each list only has a single element in it because lists of a single element are by definition already sorted. It then merges each sublist in a sorted fashion until they all become a single sorted list.

Step by step the process is:

- Divide the sorted list into lists of 1 element.
- Continually merge the lists together until they become a single list. Do the merge as follows:
- Compare the smallest items in each of the two lists to be merged.
- Move the smaller of the two to the new merged list
- Repeat until there are no unmerged items

The performance of sorting algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.

Cases | Big O Notatation |
---|---|

Best case | O(n log n) |

Average case | O(n log n) |

Worst case | O(n log n) |

The examples below were taken from Wikipedia's article about Merge sort.

Write a sample program that takes a list of numbers in the format "4, 5, 3, 1, 2". It should then sort the numbers and output them:

```
$ ./merge-sort.lang "4, 5, 3, 1, 2"
1, 2, 3, 4, 5
```

The solution should handle duplicate elements

```
$ ./merge-sort.lang "4, 5, 3, 1, 4, 2"
1, 2, 3, 4, 4, 5
```

In addition, there should be some error handling for situations where the user doesn't supply correct input.

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Merge Sort. In order to keep things simple, we split up the testing as follows:

- Merge Sort Valid Tests
- Merge Sort Invalid Tests

Description | Input | Output |
---|---|---|

Sample Input | "4, 5, 3, 1, 2" | "1, 2, 3, 4, 5" |

Sample Input: With Duplicate | "4, 5, 3, 1, 4, 2" | "1, 2, 3, 4, 4, 5" |

Sample Input: Already Sorted | "1, 2, 3, 4, 5" | "1, 2, 3, 4, 5" |

Sample Input: Reverse Sorted | "9, 8, 7, 6, 5, 4, 3, 2, 1" | "1, 2, 3, 4, 5, 6, 7, 8, 9" |

Description | Input |
---|---|

No Input | |

Empty Input | "" |

Invalid Input: Not A List | "1" |

Invalid Input: Wrong Format | "4 5 3" |

All of these tests should output the following:

```
Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"
```

- Merge Sort in Algol68
- Merge Sort in C
- Merge Sort in C#
- Merge Sort in C++
- Merge Sort in Euphoria
- Merge Sort in Go
- Merge Sort in Groovy
- Merge Sort in Haskell
- Merge Sort in Java
- Merge Sort in Javascript
- Merge Sort in Kotlin
- Merge Sort in Mathematica
- Merge Sort in Matlab
- Merge Sort in Objective C
- Merge Sort in Php
- Merge Sort in Python
- Merge Sort in Rust