Algorithm Implementation/Sorting/Merge sort

Merge Sort

You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.

Key Comparing

Keys are compared in the following way: Let k_a be the key of the one item, called item A, let k_b be the key of the other item, called item B. Let k_a(i) be the i^th entry in the key k_a, where the first entry is at index 0. Let i = 0. If the keys are less than i elements long then the keys are equal. If k_a(i) < k_b(i), then item A is ordered before item B. If k_a(i) > k_b(i), then item B is ordered before item A. If k_a(i) = k_b(i), then add one to i, and return the line under "Let i = 0."

Time Cost

Let n_i be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let n_k be the number of keys in each item.

The total time to sort the sequence is thus O(n_k(n_i + N)).

Common Lisp

Naive implementation, translation of pseudocode found at Wikipedia.

(defmacro
  apenda-primeiro (ret1 left1)
  "Appends first element of left1 to right1, and removes first element from left1."
  `(progn
    (setf ,ret1 (if (eq ,ret1 nil) (cons (car ,left1) nil) (append ,ret1 (cons (car ,left1) nil))))
    (setf ,left1 (cdr ,left1))))
 
(defun
    merge-func (left right)
  "Our very own merge function, takes two lists, left and right, as arguments, and returns a new merged list."
  (let (ret)
    (loop
      (if (or (not (null left)) (not (null right)))
          (progn
           (if (and (not (null left)) (not (null right)))
               (if (<= (car left) (car right))
                   (apenda-primeiro ret left)
                 (apenda-primeiro ret right))
             (if (not (null left))
                 (apenda-primeiro ret left)
               (if (not (null right))
                   (apenda-primeiro ret right)))))
        (return)))
    ret))
(defun
    merge-sort (m)
  "Merge-sort proper. Takes a list m as input and returns a new, sorted list; doesn't touch the input."
  (let* ((tam (length m))
         (mid (ceiling (/ tam 2)))
         (left)
         (right))
    (if (<= tam 1)
        m
      (progn
       (loop for n from 0 to (- mid 1) do
         (apenda-primeiro left m))
       (loop for n from mid to (- tam 1) do
         (apenda-primeiro right m))
       (setf left (merge-sort left))
       (setf right (merge-sort right))
       (merge-func left right)))))

C

///function:
mergeSort(name_array);
 
 //tipo Data used:
typedef struct data{
      char*some;
      int data;
} DATA;
typedef struct _nodo{
       int key;
       DATA data;
}nodo;
 
///n is kept as global
int n;
 
void merge(nodo*a,nodo*aux,int left,int right,int rightEnd){
  int i,num,temp,leftEnd=right-1;
  temp=left;
  num=rightEnd-left+1;
  while((left<=leftEnd)&&(right<=rightEnd)){
    if(a[left].key<=a[right].key){
       aux[temp++]=a[left++];
    }
    else{
        aux[temp++]=a[right++];
    }
  }
  while(left<=leftEnd){
        aux[temp++]=a[left++];
  }
  while(right<=rightEnd){
        aux[temp++]=a[right++];
  }
  for (i=1;i<=num;i++,rightEnd--){
    a[rightEnd]=aux[rightEnd];
  }
}
void mSort(nodo*a,nodo*aux,int left,int right){
  int center;
  if (left<right){
    center=(left+right)/2;
    mSort(a,aux,left,center);
    mSort(a,aux,center+1,right);
    merge(a,aux,left,center+1,right);
  }
}
void mergeSort(nodo*p){
    nodo*temp=(nodo*)malloc(sizeof(nodo)*n);
    mSort(p,temp,0,n-1);
    free(temp);
}

Fortran

subroutine Merge(A,NA,B,NB,C,NC)
 
   integer, intent(in) :: NA,NB,NC         ! Normal usage: NA+NB = NC
   integer, intent(in out) :: A(NA)        ! B overlays C(NA+1:NC)
   integer, intent(in)     :: B(NB)
   integer, intent(in out) :: C(NC)
 
   integer :: I,J,K
 
   I = 1; J = 1; K = 1;
   do while(I <= NA .and. J <= NB)
      if (A(I) <= B(J)) then
         C(K) = A(I)
         I = I+1
      else
         C(K) = B(J)
         J = J+1
      endif
      K = K + 1
   enddo
   do while (I <= NA)
      C(K) = A(I)
      I = I + 1
      K = K + 1
   enddo
   return
 
end subroutine merge
 
recursive subroutine MergeSort(A,N,T)
 
   integer, intent(in) :: N
   integer, dimension(N), intent(in out) :: A
   integer, dimension((N+1)/2), intent (out) :: T
 
   integer :: NA,NB,V
 
   if (N < 2) return
   if (N == 2) then
      if (A(1) > A(2)) then
         V = A(1)
         A(1) = A(2)
         A(2) = V
      endif
      return
   endif      
   NA=(N+1)/2
   NB=N-NA
 
   call MergeSort(A,NA,T)
   call MergeSort(A(NA+1),NB,T)
 
   if (A(NA) > A(NA+1)) then
      T(1:NA)=A(1:NA)
      call Merge(T,NA,A(NA+1),NB,A,N)
   endif
   return
 
end subroutine MergeSort
 
program TestMergeSort
 
   integer, parameter :: N = 8
   integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
   integer, dimension ((N+1)/2) :: T
   call MergeSort(A,N,T)
   write(*,'(A,/,10I3)')'Sorted array :',A
 
end program TestMergeSort

Scheme

(define (mergesort x)
  (if (= 0 (length x))
      '()
      ;else
      (if (= (length x) 1)
          x
          ;else
          (combine (mergesort (firstHalf x (/ (length x) 2))) (mergesort (lastHalf x (/ (length x) 2)))
                   )
          )
      )
)
(define (combine list1 list2)
  (if (null? list1) list2
      ;else
      (if (null? list2) list1
          ;else
          (if (<= (car list1) (car list2))
              ;car of list 1 is second element of list 2
              (cons (car list1) (combine (cdr list1) list2))
              ;else
              (cons (car list2) (combine list1 (cdr list2)))
      )
          )
      )
        )
 
(define (firstHalf L N)
  (if (= N 0)
      null
   )
  (if (or (= N 1) (< N 2)) 
      (list (car L))
      ;else
      (cons (car L) (firstHalf (cdr L) (- N 1)))))
 
(define (lastHalf L N)
  (if (= N 0) L); Base Case
  (if (or (= N 1) (< N 2))
      (cdr L)
      ;else
      (lastHalf (cdr L) (- N 1)))
      )

Haskell

sort :: Ord a => [a] -> [a]

sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where
    (ys,zs) =  splitAt (length xs `div` 2) xs
    merge [] y=y
    merge x []=x
    merge (x:xs) (y:ys)
      | x<=y = x:merge xs (y:ys)
      | otherwise = y:merge (x:xs) ys

A slightly more lazy version that doesn't check the length of the list each iteration:

sort :: Ord a => [a] -> [a]

sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where
    (ys,zs) = (odds xs, evens xs)

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
      | x<=y = x:merge xs (y:ys)
      | otherwise = y:merge (x:xs) ys

odds [] = []
odds [x] = [x]
odds (x:_:xs) = x:odds xs

evens = odds . drop 1

Prolog

This is an ISO-Prolog compatible implementation of merge sort with the exception of the predicate append(-list, -list, -list), which is available in most Prolog implementations. Special prolog dialects might provide some of the predicates used in this implementation.

 % Merge-Sort: ms(<source>, <result>) %
 ms([], []).
 ms(Xs, Rs) :- len(Xs, L), ms(Xs, Rs, L), !. 
 
 % Merge-Sort: ms(<source>, <result>, len). Here len is the number of elements in <source> which will be sorted %
 ms([], [], _).
 ms(Xs, Xs, 0) :- !.
 ms(Xs, Xs, 1) :- !.
 ms(Xs, Ys, N) :- N > 1, N1 is N//2, N2 is N-N1,
                        split(Xs, XAs, XBs, XCs, N1, N),
                        ms(XAs, XAMs, N1),
                        ms(XBs, XBMs, N2),
                        merge(XAMs, XBMs, Yss),
                        append(Yss, XCs, Ys), !.
 
 % Merge of lists: merge(<list1>, <list2>, <result>) %
 merge([], Xs, Xs).
 merge(Xs, [], Xs).
 merge([X|Xs], [Y|Ys], Zs) :- X =< Y -> 
                                (merge(Xs, [Y|Ys], Zss), append([X], Zss, Zs), !);
                                (merge([X|Xs], Ys, Zss), append([Y], Zss, Zs), !).
 
 % Splits a list into three chunks at the positions given. Positions need not be within the bounds of the list %
 split([], [], [], [], _, _).
 split(Xs, [], [], Xs, 0, 0).
 split(Xs, [], As, Bs, 0, N) :- 0 =< N, split(Xs, As, Bs, N), !.
 split(Xs, As, [], Bs, N, N) :- 0 =< N, split(Xs, As, Bs, N), !.
 split(Xs, As, Bs, Cs, N, M) :- 0 < N, N =< M,
                        Xs = [X|Xss], As = [X|Ass],
                        N1 is N-1, M1 is M-1,
                        split(Xss, Ass, Bs, Cs, N1, M1), !. 
 
 % Length of a list %
 len([], 0).
 len([_|Xs], N) :- len(Xs, N1), N is N1+1.

The above implementation assumes that comparison is done with the '=<' operator. Instead, one can pass in a rule for comparing
list entries. Evaluation might then be effected as follows:

 % comp(+functor, +atomic, + atomic, -integer): Compares atomic values
 % functor: A 3-arguent predicate; this predicate implements the comparison
 % atomic : Atomic values
 % integer: Result, interpreted according to sign 
 comp(F, X, Y, I) :- functor(F, N, 3), arg(1, F, X), arg(2, F, Y), arg(3, F, I), call(F).

Python

A "standard" mergesort:

def mergesort(w):
    """Sort list w and return it."""
    if len(w)<2:
        return w
    else:    
        mid=len(w)//2
        # sort the two halves of list w recursively with mergesort and merge them
        return merge(mergesort(w[:mid]), mergesort(w[mid:]))

An alternative method, using a recursive algorithm to perform the merging in place (except for the O(log n) overhead to trace the recursion) in O(n log n) time:

def merge(lst, frm, pivot, to, len1, len2):
    if len1==0 or len2==0: return
    if len1+len2 == 2:
        if lst[pivot])<lst[frm]: lst[pivot], lst[frm] = lst[frm], lst[pivot]
        return
    if len1 > len2:
        len11 = len1/2
        firstcut, secondcut, length = frm+len11, pivot, to-pivot
        while length > 0:
            half = length/2
            mid = secondcut+half
            if lst[mid]<lst[firstcut]: secondcut, length = mid+1, length-half-1
            else: length = half
        len22 = secondcut - pivot
    else:
        len22 = len2/2
        firstcut, secondcut, length = frm, pivot+len22, pivot-frm
        while length > 0:
            half = length/2
            mid = firstcut+half
            if lst[secondcut]<lst[mid]: length = half
            else: firstcut, length = mid+1, length-half-1
        len11 = firstcut-frm
    if firstcut!=pivot and pivot!=secondcut:
        n, m = secondcut-firstcut, pivot-firstcut
        while m != 0: n, m = m, n%m
        while n != 0:
            n -= 1
            p1, p2 = firstcut+n, n+pivot
            val, shift = lst[p1], p2-p1
            while p2 != firstcut+n:
                lst[p1], p1 = lst[p2], p2
                if secondcut-p2>shift: p2 += shift
                else: p2 = pivot-secondcut+p2
            lst[p1] = val
    newmid = firstcut+len22
    merge(lst, frm, firstcut, newmid, len11, len22)
    merge(lst, newmid, secondcut, to, len1-len11, len2-len22)
 
def sort(lst, frm=0, to=None):
    if to is None: to = len(lst)
    if to-frm<2: return
    middle = (frm+to)/2
    sort(lst, frm, middle)
    sort(lst, middle, to)
    merge(lst, frm, middle, to, middle-frm, to-middle)

Ruby

def mergesort(list)
  return list if list.size <= 1
  mid = list.size / 2
  left  = list[0, mid]
  right = list[mid, list.size-mid]
  merge(mergesort(left), mergesort(right))
end
 
def merge(left, right)
  sorted = []
  until left.empty? or right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted.concat(left).concat(right)
end

Miranda

sort []    = []
sort [x]   = [x]
sort array = merge (sort left) (sort right)
             where
               left  = [array!y | y <- [0..mid]]
               right = [array!y | y <- [(mid+1)..max]]
               max   = #array - 1
               mid   = max div 2

Standard ML

fun mergesort [] = []
|   mergesort [x] = [x]
|   mergesort lst = 
    let fun merge ([],ys) = ys (*merges two sorted lists to form a sorted list *)
        |   merge (xs,[]) = xs
        |   merge (x::xs,y::ys) = 
              if x<y then
                x::merge (xs,y::ys)
              else
                y::merge (x::xs,ys)
        ; 
        val half = length(lst) div 2;
     in
        merge (mergesort (List.take (lst, half)),mergesort (List.drop (lst, half)))
     end
;

Java

public int[] mergeSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
        // if the array has more than 1 element, we need to split it and merge the sorted halves
        if(array.length > 1)
        {
                // number of elements in sub-array 1
                // if odd, sub-array 1 has the smaller half of the elements
                // e.g. if 7 elements total, sub-array 1 will have 3, and sub-array 2 will have 4
                int elementsInA1 = array.length / 2;
                // we initialize the length of sub-array 2 to
                // equal the total length minus the length of sub-array 1
                int elementsInA2 = array.length - elementsInA1;
                // declare and initialize the two arrays once we've determined their sizes
                int arr1[] = new int[elementsInA1];
                int arr2[] = new int[elementsInA2];
                // copy the first part of 'array' into 'arr1', causing arr1 to become full
                for(int i = 0; i < elementsInA1; i++)
                        arr1[i] = array[i];
                // copy the remaining elements of 'array' into 'arr2', causing arr2 to become full
                for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
                        arr2[i - elementsInA1] = array[i];
                // recursively call mergeSort on each of the two sub-arrays that we've just created
                // note: when mergeSort returns, arr1 and arr2 will both be sorted!
                // it's not magic, the merging is done below, that's how mergesort works :)
                arr1 = mergeSort(arr1);
                arr2 = mergeSort(arr2);
 
                // the three variables below are indexes that we'll need for merging
                // [i] stores the index of the main array. it will be used to let us
                // know where to place the smallest element from the two sub-arrays.
                // [j] stores the index of which element from arr1 is currently being compared
                // [k] stores the index of which element from arr2 is currently being compared
                int i = 0, j = 0, k = 0;
                // the below loop will run until one of the sub-arrays becomes empty
                // in my implementation, it means until the index equals the length of the sub-array
                while(arr1.length != j && arr2.length != k)
                {
                        // if the current element of arr1 is less than current element of arr2
                        if(arr1[j] < arr2[k])
                        {
                                // copy the current element of arr1 into the final array
                                array[i] = arr1[j];
                                // increase the index of the final array to avoid replacing the element
                                // which we've just added
                                i++;
                                // increase the index of arr1 to avoid comparing the element
                                // which we've just added
                                j++;
                        }
                        // if the current element of arr2 is less than current element of arr1
                        else
                        {
                                // copy the current element of arr1 into the final array
                                array[i] = arr2[k];
                                // increase the index of the final array to avoid replacing the element
                                // which we've just added
                                i++;
                                // increase the index of arr2 to avoid comparing the element
                                // which we've just added
                                k++;
                        }
                }
                // at this point, one of the sub-arrays has been exhausted and there are no more
                // elements in it to compare. this means that all the elements in the remaining
                // array are the highest (and sorted), so it's safe to copy them all into the
                // final array.
                while(arr1.length != j)
                {
                        array[i] = arr1[j];
                        i++;
                        j++;
                }
                while(arr2.length != k)
                {
                        array[i] = arr2[k];
                        i++;
                        k++;
                }
        }
        // return the sorted array to the caller of the function
        return array;
}

JavaScript

;(function() {
 
  var defaultComparator = function (a, b) {
    if (a < b) {
      return -1;
    }
    if (a > b) {
      return 1;
    }
    return 0;
  }
 
  Array.prototype.mergeSort = function( comparator ) {
    var i, j, k,
        firstHalf,
        secondHalf,
        arr1,
        arr2;
 
    if (typeof comparator != "function") { comparator = defaultComparator; }
 
    if (this.length > 1) {
      firstHalf = Math.floor(this.length / 2);
      secondHalf = this.length - firstHalf;
      arr1 = [];
      arr2 = [];
 
      for (i = 0; i < firstHalf; i++) {
        arr1[i] = this[i];
      }
 
      for(i = firstHalf; i < firstHalf + secondHalf; i++) {
        arr2[i - firstHalf] = this[i];
      }
 
      arr1.mergeSort( comparator );
      arr2.mergeSort( comparator );
 
      i=j=k=0;
 
      while(arr1.length != j && arr2.length != k) {
        if ( comparator( arr1[j], arr2[k] ) <= 0 ) {
          this[i] = arr1[j];
          i++;
          j++;
        } 
        else {
          this[i] = arr2[k];
          i++;
          k++;
        }
      }
 
      while (arr1.length != j) {
        this[i] = arr1[j];
        i++;
        j++;
      }
 
      while (arr2.length != k) {
        this[i] = arr2[k];
        i++;
        k++;
      }
    }
  }
})();

Item aux[maxN]; Merge(Item a[], int l,int m, int r)

           { int i,j,k;
           For (i=m+1; i>1;i--)aux[i-1]=a[i-1];
           For(j=m;j<r;j++)aux[r+m-j]=a[j+1];
                     For(k=1; k<=r,k++)
                          If (aux[j]<aux[i])
                                  a[k]=aux[j--]; else a[k]=aux[i++];
            }

1. define min(A,B) (A<B)?A:B

Void mergesortBU(Item a[],int l ,int r)

           {int i,m;
                   For (m=1; m<=r-1;m=m+m)
                          For(j=1;i+=m+m)
                                 merge(a,i,i+m-1,min(i+m+m-1,r));

C++

Here is a recursive implementation of the merge sort using STL vectors (This is a naive implementation):

//! \brief Performs a recursive merge sort on the given vector
//! \param vec The vector to be sorted using the merge sort
//! \return The sorted resultant vector after merge sort is
//! complete.
vector<int> merge_sort(vector<int>& vec)
{
    // Termination condition: List is completely sorted if it
    // only contains a single element.
    if(vec.size() == 1)
    {
        return vec;
    }
 
    // Determine the location of the middle element in the vector
    std::vector<int>::iterator middle = vec.begin() + (vec.size() / 2);
 
    vector<int> left(vec.begin(), middle);
    vector<int> right(middle, vec.end());
 
    // Perform a merge sort on the two smaller vectors
    left = merge_sort(left);
    right = merge_sort(right);
 
    return merge(left, right);
}

And here is the implementation of the merge function:

//! \brief Merges two sorted vectors into one sorted vector
//! \param left A sorted vector of integers
//! \param right A sorted vector of integers
//! \return A sorted vector that is the result of merging two sorted
//! vectors.
vector<int> merge(const vector<int>& left, const vector<int>& right)
{
    // Fill the resultant vector with sorted results from both vectors
    vector<int> result;
    unsigned left_it = 0, right_it = 0;
 
    while(left_it < left.size() && right_it < right.size())
    {
        // If the left value is smaller than the right it goes next
        // into the resultant vector
        if(left[left_it] < right[right_it])
        {
            result.push_back(left[left_it]);
            left_it++;
        }
        else
        {
            result.push_back(right[right_it]);
            right_it++;
        }
    }
 
    // Push the remaining data from both vectors onto the resultant
    while(left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }
 
    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }
 
    return result;
}

Here's another recursive implementation of the mergesort using arrays of variable length

#include <iostream>
using namespace std;
 
 
void merge(int a[], const int low, const int mid, const int high)
{
        // Variables declaration. 
        int * b = new int[high+1-low];
        int h,i,j,k;
        h=low;
        i=0;
        j=mid+1;
        // Merges the two array's into b[] until the first one is finish
        while((h<=mid)&&(j<=high))
        {
                if(a[h]<=a[j])
                {
                        b[i]=a[h];
                        h++;
                }
                else
                {
                        b[i]=a[j];
                        j++;
                }
                i++;
        }
        // Completes the array filling in it the missing values
        if(h>mid)
        {
                for(k=j;k<=high;k++)
                {
                        b[i]=a[k];
                        i++;
                }
        }
        else
        {
                for(k=h;k<=mid;k++)
                {
                        b[i]=a[k];
                        i++;
                }
        }
        // Prints into the original array
        for(k=0;k<=high-low;k++) 
        {
                a[k+low]=b[k];
        }
        delete[] b;
}
 
void merge_sort(int a[], const int low, const int high)         // Recursive sort ...
{
        int mid;
        if(low<high)
        {
                mid=(low+high)/2;
                merge_sort(a, low,mid);
                merge_sort(a, mid+1,high);
                merge(a, low,mid,high);
        }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
        int arraySize;
        // a[] is the array to be sorted. ArraySize is the size of a[] ...
        merge_sort(a, 0, (arraySize-1) );        // would be more natural to use merge_sort(a, 0, arraySize ), so please try ;-)
 
        // some work 
        return 0;
}

Perl

use sort '_mergesort';
sort @array;

PHP

//Aux functions:slice and merge
//slice_array:Create a new array from an exist array key $from to $to
function slice_array($arr,$from,$to){
        if($from>$to) return $arr;
        elseif($from==$to) return $arr[$from];
        if(!is_array($arr)||count($arr)==1) {return $arr;}
        else{
                $new=array();$a=$to-$from;
                for($i=0;$i<$a;$i++){
                        $new[$i]=$arr[$from++];
                }
        }
 
        return $new;
}
//merge_array: create a new array from two exist arrays, order is $x, $y.
function merge_array($x,$y){
        $new=array();
        for($i=0;$i<count($x);$i++){
                $new[$i]=$x[$i];
        }
        for($j=0;$j<count($y);$j++){
                $new[count($x)+$j]=$y[$j];
        }
        return $new;
}
//Main Script
function MergeSort($a){
        if (count($a)>1){
                $cent=floor(count($a)/2);
                $b=MergeSort(slice_array($a,0,$cent));
                $c=MergeSort(slice_array($a,$cent,count($a)));
                return merge($b,$c,$a);
        }else{return $a;}
}
 
function merge($b,$c,$a){
        $i=$j=$k=0;
        $p=count($b);$q=count($c);
        $a=array();
        while($i<$p && $j<$q){
                if($b[$i]<=$c[$j]){
                        $a[$k]=$b[$i];
                        $i++;
                }else{
                        $a[$k]=$c[$j];
                        $j++;
                }
                $k++;
        }
        if($i==$p){
                $xxx = slice_array($c,$j,$q);
        }else{
                $xxx = slice_array($b,$i,$p);
        }
        return merge_array($a,$xxx);
}

Groovy

def mergeSort(def list){
 if (list.size() <= 1) { return list }
 else {
     center = list.size() / 2
     left  = list[0..center]
     right = list[center..list.size() - 1]
     merge(mergeSort(left), mergeSort(right))
 }
}
 
def merge(def left, def right){
  def sorted = []
  while(left.size() > 0 || right.size() > 0)
    if(left.get(0) <= right.get(0)){
      sorted << left
    }else{
      sorted << right
    }
  sorted = sorted + left + right
  return sorted
}

Eiffel

class
        APPLICATION
 
create
        make
 
feature -- Initialization
 
        make is
           --
             do
 
               end
 
feature -- Algorithm
 
        mergesort(a:ARRAY[INTEGER]; l,r:INTEGER) is
                        -- Recursive mergesort
 
                local
                        m: INTEGER
                do
                        if l<r then
                                m := (l+r)//2
                                mergesort(a,l, m)
                                mergesort(a,m+1,r)
                                merge(a,l,m,r)
 
                        end
                end
 
feature -- Utility feature
 
        merge(a:ARRAY[INTEGER]; l,m,r: INTEGER) is
                        -- The merge feature of all mergesort variants
                local
                        b: ARRAY[INTEGER]
                        h,i,j,k: INTEGER
 
                do
                        i := l
                        j := m+1
                        k := l
                        create b.make (l, r)
 
                        from
 
                        until
                                i > m or j > r
                        loop
                                -- begins the merge and copies it into an array "b"
                                if a.item (i) <= a.item (j) then
                                        b.item (k) := a.item (i)
                                        i := i +1
 
                                elseif a.item (i) > a.item (j) then
                                        b.item (k) := a.item (j)
                                        j := j+1
                                end
                                k := k+1
                        end
 
                                -- Finishes the copy of the uncopied part of the array
                        if i > m then
                                from
                                        h := j
                                until
                                        h > r
                                loop
                                        b.item (k+h-j) := a.item (h)
                                        h := h+1
                                end
 
                        elseif j > m then
 
                                from
                                        h := i
                                until
                                        h > m
                                loop
                                        b.item (k+h-i) := a.item (h)
                                        h := h+1
                                end
                        end
 
                        -- "begins the copy to the real array"
 
                        from
                                h := l
                        until
                                h > r
                        loop
                                a.item (h) := b.item (h)
                                h := h+1
                        end
 
                end
 
feature -- Attributes
 
        array: ARRAY[INTEGER]