# Merge sort (Eiffel)

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)
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",
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
```