# Archive for July, 2012

### The heap sort algorithm

Posted by helmutbrandl in Uncategorized on July 23, 2012

Introduction The heapsort algorithm is a sorting algorithm which has time complexity O(n log n) and does not need additional space. Merge sort has the same time complexity but usually needs additional space. As opposed to merge sort, the heap sort algorithm is not stable i.e. it might reverse the order of equal elements. The […]

### Lattices — Partial order with supremum and infimum

Posted by helmutbrandl in Uncategorized on July 16, 2012

Introduction Types which satisfy the concept of a partial order (i.e. which are descendants of the type PARTIAL_ORDER) have a binary relation “<=” which is reflexive, transitive and antisymmetric, i.e. for every three objects “a”, “b”, and “c” the following conditions are satisfied: reflexive: a<=a transitive: a<=b => b=>c => a=>c antisymmetric: a<=b => b=>a […]

### The insertion sort algorithm

Posted by helmutbrandl in Uncategorized on July 1, 2012

Introduction Insertion sort is one of the simplest sorting algorithms. It is quite efficient for small arrays. Its runtime increases with the square of the number of elements to be sorted. Therefore it should not be used with large data sets. For large data sets algorithms like merge sort or heap sort are far more […]