Algorithm Implementation/Sorting/Merge sort

From Wikibooks, open books for an open world
< Algorithm Implementation‎ | Sorting(Redirected from Algorithm implementation/Sorting/Merge sort)
Jump to: navigation, search

Merge Sort[edit]

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[edit]

Keys are compared in the following way: Let ka be the key of the one item, called item A, let kb be the key of the other item, called item B. Let ka(i) be the ith entry in the key ka, 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 ka(i) < kb(i), then item A is ordered before item B. If ka(i) > kb(i), then item B is ordered before item A. If ka(i) = kb(i), then add one to i, and return the line under "Let i = 0."

Time Cost[edit]

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

The total time to sort the sequence is thus O(nk(ni + N)).

Common Lisp[edit]

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)))))


Simpler Implementation in a somewhat more functional style.

(defun sort-func (frst scond &optional (sorted nil))
  "Sorts the elements from the first and second list in ascending order and puts them in `sorted`"
  (cond ((and (null frst) (null scond)) sorted)
        ((null frst) (append (reverse sorted) scond))
        ((null scond) (append (reverse sorted) frst))
        (t (let ((x (first frst))
                 (y (first scond)))
             (if (< x y)
                 (sort-func (rest frst) scond (push x sorted))
                 (sort-func frst (rest scond) (push y sorted)))))))
 
(defun merge-sort (lst)
  "Divides the elements in `lst` into individual elements and sorts them"
  (when (not (null lst))
    (let ((divided (mapcar #'(lambda (x) (list x)) lst)))
      (labels ((merge-func (div-list &optional (combined '())) ; merges the elements in ascending order
                 (if div-list
                     (merge-func (rest (rest div-list)) (push (sort-func (first div-list) (second div-list)) combined))
                     combined))
               (final-merge (div-list) ; runs merge-func until all elements have been reconciled
                 (if (> (length div-list) 1)
                     (final-merge (merge-func div-list))
                     div-list)))
        (final-merge divided)))))

C[edit]

///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[edit]

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[edit]

(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[edit]

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 efficient version only traverses the input list once to split (note that length takes linear time in Haskell):

sort :: Ord a => [a] -> [a]
sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where (ys,zs) = split 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
 
split []        =  ([], [])
split [x]       =  ([x], [])
split (x:y:xs)  =  (x:l, y:r)
  where (l, r)  =  split xs

Prolog[edit]

This is an ISO-Prolog compatible implementation of merge sort.

mergesort(L, Sorted) :-
    once(mergesort_r(L, Sorted)).
 
mergesort_r([], []).
mergesort_r([X], [X]).
mergesort_r(L, Sorted) :-
    split(L, Left, Right),
    mergesort_r(Left, SortedL),
    mergesort_r(Right, SortedR),
    merge(SortedL, SortedR, Sorted).
 
% Split list into two roughly equal-sized lists.
split([], [], []).
split([X], [X], []).
split([X,Y|Xs], [X|Left], [Y|Right]) :-
    split(Xs, Left, Right).
 
% Merge two sorted lists into one.
merge(Left, [], Left).
merge([], Right, Right).
merge([X|Left], [Y|Right], [Z|Merged]) :-
    (X @< Y ->
        Z = X,
        merge(Left, [Y|Right], Merged)
    ;
        Z = Y,
        merge([X|Left], Right, Merged)
    ).

Python[edit]

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[edit]

def merge_sort(array)
  return array if array.size <= 1
  left = merge_sort array[0, array.size / 2]
  right = merge_sort array[array.size / 2, array.size]
 
  merge(left, right)
end
 
 
def merge(left, right)
  result = []
 
  while left.size > 0 && right.size > 0
    result << if left[0] <= right[0]
      left.shift
    else
      right.shift
    end
  end
 
  result.concat(left).concat(right)
end

Miranda[edit]

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[edit]

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[edit]

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[edit]

;(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++;
      }
    }
  }
})();

Separate into two functions:

function mergesort(list){
    if (list.length <= 1)
        return list;
 
    var mid = Math.floor(list.length / 2),
        left  = list.slice(0, mid),
        right = list.slice(mid, list.length);
 
    return merge(mergesort(left), mergesort(right))
}
 
function merge(left, right){
    var sorted = [];
    while (left && left.length > 0 && right && right.length > 0){
        var b = left[0] <= right[0];
        sorted.push(b? left[0]: right[0]);
        // remove the element which was added to the sorted array
        b? left.splice(0, 1): right.splice(0, 1);
    }
    return sorted.concat(left, right);
}

C++[edit]

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(vec,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(vector<int> &vec,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++;
    }
    //show merge process..
      int i;
      for(i=0;i<result.size();i++)
         {                                
	     cout<<result[i]<<" ";
         }
    // break each line for display purposes..
        cout<<"***********"<<endl; 
 
    //take a source vector and parse the result to it. then return it.  
	vec = result;				
	return vec;
}

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[edit]

use sort '_mergesort';
sort @array;

PHP[edit]

//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[edit]

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[edit]

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]