Fibonacci numbers

Mathematica
Note, that this implementation exists. Algorithm is:

Fibonacci[n_] := Round[GoldenRatio^n/Sqrt[5]]

Be aware, that this formula:

can not be trivially applied in other languages.

Java
In Java, we have arbitrarily large integers and decimals, but prebuilt classes lack the functionality (it's a shame). For example we can not easily take root of 5. To do this, we would need to use a library like JScience or write Newton approximation method (what can be quite error prone process).


C#
In C#, there is no arbitrarily large decimals. It does have class decimal (with 28-29 significant digits), but assuming that Math class supports it, is just asking too much (it's a shame). But thumbs up, for it at least has BigInteger.

Binary search

Java
In java, Collections/Arrays class contains binary search.

Collections.binarySearch(list, key);
Arrays.binarySearch(array, key);

My naive generic implementation is recursive and ignores the fact, that I should use ListIterator for data structures, that do not have random access (ex. LinkedList).

C#
In C#, list itself and Arrays class contains binary search.

list.BinarySearch(key);
Array.BinarySearch(array, key);

My naive Java implementation translated to C#.

Mathematica
In mathematica, Combinatorica library contains binary search.

BinarySearch[list, key]

Merge sort

Will take O(n * log (n)) time, and does not depend on input.

Java

C#

Insertion sort

Efficient for small lists, with size less then 30.

Special cases are:

• if list is almost sorted, it will be near linear time
• if sorted list is reversed, it will be quadratic time

Java

C#