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.
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:
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.
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][1].
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.
The following table contains various test cases that you can use to verify the correctness of your solution:
Description | Input | Output |
---|---|---|
No Input | Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5” | |
Empty Input | ”” | Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5” |
Invalid Input: Not a list | 1 | Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5” |
Invalid Input: Wrong Format | 4 5 3 | Usage: please provide a list of at least two integers to sort in the format “1, 2, 3, 4, 5” |
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 |