It is a question where given the roman numeral character, find the integer value.

Some are just straight forward. Ex. III = 1 + 1 + 1 = 3.

Others require more calculation. Ex. IV != 1 + 5 = 6. IV = 4.

Each digits from left to right should flow from largest to smallest, except for cases like IV, where it is 5–1 instead of 5+1, when the order is reversed.

Below is my implementation of solution in Java. It took 13ms, which is a little below average for the success submission in LeetCode. I will comeback to optimize the solution.

Merge sort splits the list into two, again and again until each list has only one item. Then each items are sorted and merged, until it is merged to total list. It has time complexity of O(nlog(n)), which is efficient.

Below is implementation of merge sort in Javascript.

Insertion sort goes through the list and inserts items to the new list, one by one. It has time complexity of O(n) on average, and O(n²) on the worst case. Compared to merge sort or quick sort, its time complexity is not great. It is good for

List that is already almost sorted.

List of small number of elements.

Below is the implementation of insertion sort in Javascript.