Merge sort (Eiffel)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

Merge sort or mergesort is a simple but efficient sort algorithm that splits the list into two sublists, sorts each one, then combines them into a single sorted list. It has good worst-case performance and requires only sequential access, making it ideal for sequential data structures like linked lists. In this Eiffel example we'll write a simple mergesort for arrays.

This implementation uses Eiffel generic facilities to enable sorting of arrays of elements of any type that inherits from COMPARABLE, providing flexibility while ensuring that comparison operators are meaningful.

Operating recursively we split a given subarray in half and apply merge sort to each half, then merge the two halves back together. We provide a base case for the recursion in this example in terms of 2 element subarrays which are sorted by swapping the elements if they are out of order - more efficient implementations may resort to other sorting algorithms, such as insertion sort, once the subarray size falls below a given threshold.

<<recursively sort subarrays>>=
merge_sort_subarray(a : ARRAY[X]; min, max : INTEGER) is
    local
        middle : INTEGER
    do
        if max - min > 1 then
            middle := min + (max - min) #// 2
            merge_sort_subarray(a, min, middle)
            merge_sort_subarray(a, middle, max)
            merge(a, min, max, middle)
        elseif max - min = 1 and a@min > a@max then
            a.swap(min,max)
        end
    end -- merge_sort_subarray

Much of the work in sorting is done in the merging back together of the two sorted subarrays. In this case we do so by scanning through the two subarrays to be merged and inserting elements from the second subarray into the first where appropriate. The merge should, of course, ensure that merged portion of the whole array should now be sorted.

<<merge subarrays>>=
merge(a : ARRAY[X]; min, max, middle : INTEGER) is
    require
        min < max and middle.in_range(min, max + 1)
    local
        i, j, pivot : INTEGER
        value : X
    do         
        from
            i := min
            j := middle
            pivot := middle
        invariant
            i <= j and a.valid_index(i) and a.valid_index(j)
        until
            i >= pivot or j >= max
        loop
            if a@i < a@j or i > pivot then
                i := i + 1
            else              
                value := a@j
                a.remove(j)
                a.add(value, i)
                i := i + 1
                j := j + 1
                pivot := pivot + 1
            end
        end
    ensure
        a.count = old a.count
        is_sorted(a, min, max)
    end -- merge

We provide a routine to check that a portion of an array is sorted so that the contract from the merge can be checked durign debugging:

<<verify sorting>>=
is_sorted(a: ARRAY[X]; min, max : INTEGER) : BOOLEAN is
    require
        a /= Void
    local
        i : INTEGER
    do
        Result := True
        from 
            i := min
        invariant
            a.valid_index(i)
        until
            i >= max or not Result
        loop
            if not (a@i <= a@(i+1)) then
                Result := False
            end
            i := i + 1
        end
    end -- is_sorted

Finally, since Eiffel is an objet oriented language, we must package these routines in a class and provide a suitable frontend to merge_sort_subarray to be exported as a public feature. We can make use of the sorting verification in the contract for the public feature.

<<merge_sort.e>>=
class MERGE_SORT[X -> COMPARABLE]
feature {ANY}
    merge_sort(a : ARRAY[X]) is
        require
            a /= Void
        do
            merge_sort_subarray(a, a.lower, a.upper)
        ensure
            a.count = old a.count
            is_sorted(a, a.lower, a.upper)
        end -- insertion_sort
feature {NONE}
    verify sorting
    recursively sort subarrays
    merge subarrays
end -- class MERGE_SORT

Testing

To test the MERGE_SORT class we can construct a simple test class demonstrating bubble sort running first over an array of integers, then over an array of strings.

<<merge_sort_test.e>>=
class MERGE_SORT_TEST
creation
    make
feature
    make is
        local
            i : INTEGER
            testarray_numeric : ARRAY[INTEGER_8]
            testarray_string : ARRAY[STRING]
            sorter_numeric : MERGE_SORT[INTEGER_8]
            sorter_string : MERGE_SORT[STRING]
        do
            create sorter_numeric
            create sorter_string
            testarray_numeric := <<3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9,
                                   4,6,3,0,5,7,9,3,2,5,7,9,0,1,9,3,1>>
            sorter_numeric.merge_sort(testarray_numeric)
            from
                i := testarray_numeric.lower
            until
                i >= testarray_numeric.upper
            loop
                io.put_integer(testarray_numeric@i)
                io.put_string(",")
                i := i + 1
            end
            io.put_integer(testarray_numeric.last)
            io.put_new_line
            testarray_string := <<"Paris","London","Stockholm","Berlin","Oslo",
                               "Rome","Madrid","Tallinn","Amsterdam","Dublin">>
            sorter_string.merge_sort(testarray_string)
            from
                i := testarray_string.lower
            until
                i >= testarray_string.upper
            loop
                io.put_string(testarray_string@i)
                io.put_string(",")
                i := i + 1
            end
            io.put_string(testarray_string.last)
            io.put_new_line
        end
end -- class MERGE_SORT_TEST

Download code