مهاجر

Merge sort

 

مرتب‌سازی ادغام یک الگوریتم مرتب‌سازی همسنجشی با زمان اجرای nlgn می‌باشد. در اکثر پیاده سازی‌ها این الگوریتم پایدار می‌باشد. بدین معنی که این الگوریتم ترتیب ورودی‌های مساوی را در خروجی مرتب شده حفظ می‌کند. این یک مثال از الگوریتم تقسیم و تسخیر می‌باشد. این الگوریتم در سال ۱۹۴۵ توسط جان فون نویمان اختراع شده‌است

 

 

از نظر مفهومی یک الگوریتم مرتب‌سازی ادغام بدین صورت کار می‌کند:

۱ -اگر طول لسیت ۰ یا ۱ باشد آن پیش از این مرتب شده‌است در غیر این صورت

۲-لیست نامرتب را به دو زیرلیست که اندازهٔ آن‌ها در حدود نصف سایز لیست اولیه‌است تقسیم می‌کند.

۳-هر زیرلیست را به طور بازگشتی با صدا کردن merg sort مرتب می‌کند.

۴-دو تا دوتا زیر لیست‌ها را از آخر ادغام می‌کند تا به یک لیست برسد.

مرتب سازی ادغام ۲ تا ایدهٔ اصلی را با هم ترکیب می‌کند تا زمان اجرایش تقویت شود.

۱-یک لیست کوچک از گام‌های کم‌تری برای مرتب‌کردن نسبت به یک لیست بزرگ استفاده می‌کند.

۲-یرای مرتب کردن دو لیست مرتب‌شده نسبت به دو لیست نامرتب گام‌های کمتری نیاز می‌باشد به عنوان مثال اگر این لیست‌ها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبار پیمایش کنید.

 

مجموعه <A=<5,2,4,7,1,3,2,6 را با استفاده از الگوریتم مرتب سازی ادغام مرتب کنید.

ابتدا این آرایه را نصف می کنیم پس دو آرایه به طول 4 بدست می‌آید، که برابر است با (5,2,4,7) و(1,3,2,6) سپس این روال را تا جایی ادامه می دهیم که که طول آرایه‌هایمان برابر یک شود.که برابر است با: (6)(2)(3)(1)(7)(4)(2)(5) حال به صورت زیر آنها را با هم ادغام می کنیم تا به آرایه اصلی مان برسیم.

 

در مرتب کردن n تا عنصر مرتب سازی ادغام در حالت میانگین و بدترین حالت دارای زمان اجرای (nlgn) می‌باشد.اگر زمان اجرای مرتب‌سازی ادغام برای یک لیست به طولT(n),n باشد بنابراین رابطهٔ بازگشتی T(n) = 2T(n / 2) + nاز تعریف الگوریتم پیروی می‌کند. در این الگوریتم هر دفعه لیست را به دو زیرلیست تقسیم می‌کنیم و در هر مرحله n تا گام برای ادغام کردن لازم می‌باشد.

این شکل از رابطه از تئوری قضیه اصلی پیروی می‌کند. در بدترین حالت این الگوریتم تقریبا (n ⌈lg n⌉ - ۲^⌈lg n⌉ + ۱) مقایسه دارد که بین ((nlgn+n+O(n) و (nlgn-n+۱) می‌باشد. برای n بزرگ و یک لیست که به صورت تصادفی مرتب شده‌است یعنی ممکن است به هر ترتیبی باشد تعداد مقایسه مورد انتظار mergsort بهαn کمتر از بدترین حالت می‌رسد که α از رابطهٔ روبرو بدست می‌آید:

در بدترین حالت تعداد مقایسه‌های مرتب‌سازی ادغام حدود ۰/۳۹ کمتر از مرتب سازی سریع در حالت متوسط می‌باشد. مرتب‌سازی ادغام همیشه تعداد مقایسه‌های کمتری را نسبت به مرتب‌ساز سریع احتیاج دارد، به جز در حالتی که تمام عناصر ورودی برابر باشند جایی که بدترین حالت مرتب‌سازی ادغام همراه با بهترین حالت مرتب سازی سریع پیدا می‌شود. پیچیدگی مرتب‌سازی ادغام در بدترین حالت از (O(nlgn می‌باشد که با بهترین حالت مرتب‌سازی سریع برابر می‌باشد اما در بهترین حالت تعداد مقایسه‌ها نصف تعداد مقایسه‌ها در بدترین حالت می‌باشد. در پیاده‌سازی بازگشتی مرتب‌سازی ادغام در بدترین حالت ۲n-۱ بار تابع مرتب‌سازی ادغام صدا زده می‌شود در حالی که در مرتب‌سازی سریع تابع مورد نیاز n بار صدا زده می‌شود. پیاده سازی غیر بازگشتی مرتب‌سازی ادغام از هزینهٔ سربار فراخوان تابع جلوگیری می‌کند که این کار سخت نمی‌باشد پیاده‌سازی رایج مرتب‌سازی ادغام به صورت درجا می‌باشد بنابراین سایز حافظه ورودی باید برای خروجی مرتب شده تخصیص داده شود. مرتب‌سازی درجا ممکن می‌باشد اما بسیار پیچیده‌است و در عمل از کارایی کمتری برخوردار می‌باشد حتی اگر در زمان nlgn اجرا شود. در این مواقع الگوریتم‌هایی شبیه مرتب سازی هرمی با سرعت قابل مقایسه پیشنهاد می‌شود که ازپیچیدگی کمتری برخوردار می‌باشد. برخلاف ادغام استاندارد ادغام درجا پایدار نیست.

 

 

ویکی‌پدیا ی انگلیسی

مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش

 

 

Pseudocode

function mergesort(m)
    var list left, right
    if length(m) ≤ 1
        return m
    else
        middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result

There are several variants for the merge() function, the simplest variant could look like this:

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    if length(left) > 0 
        append left to result
    if length(right) > 0 
        append right to result
    return result

[edit] Ada

Ada implementation uses type Data_T for the data array.

function Mergesort (Data : in Data_T) return Data_T is
begin
   if Data'Length <= 1 then 
      return Data;
   else
      declare
	 Middle : Integer := (Data'First + Data'Last) / 2;
	 Left  : Data_T := Data (Data'First .. Middle);
	 Right : Data_T := Data (Middle + 1 .. Data'Last);
      begin
	 Left  := Mergesort (Left);
	 Right := Mergesort (Right);
	 return Merge(Left, Right);
      end;
   end if;
end Mergesort;

Definition of the Merge function:

function Merge (Left : Data_T; Right : Data_T) return Data_T is
   Result : Data_T (1 .. Left'Length + Right'Length);
   L : Integer := Left'First;
   R : Integer := Right'First;
   I : Integer := Result'First;
begin
   while L <= Left'Last and R <= Right'Last loop
      if Left(L) <= Right(R) then
	 Result(I) := Left(L);
	 L := L + 1;
	 I := I + 1;
      else
	 Result(I) := Right(R);
	 R := R + 1;
	 I := I + 1;
      end if;
   end loop;
   if L <= Left'Last then
      Result(I..Result'Last) := Left(L..Left'Last);
   end if;
   if R <= Right'Last then
      Result(I..Result'Last) := Right(R..Right'Last);
   end if;
   return Result;
end Merge;

[edit] C

// Mix two sorted tables in one and split the result into these two tables.
int *Mix(int *tab1,int *tab2,int count1,int count2)
{
  int i,i1,i2;
  i = i1 = i2 = 0;
  int * temp = (int *)malloc(sizeof(int)*(count1+count2));

  while((i1<count1) && (i2<count2))
  {
    while((i1<count1) && (*(tab1+i1)<(tab2+i2)))
    {
      *(temp+i++) = *(tab1+i1);
      i1++;
    }
    if (i1<count1)
    {
      while((i2<count2) && (*(tab2+i2)<(tab1+i1)))
      {
        *(temp+i++) = *(tab2+i2);
        i2++;
      }
    }
  }

  memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int));
  memcpy(tab1,temp,count1*sizeof(int));

  memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int));
  memcpy(tab2,temp+count1,count2*sizeof(int));
  // These two lines can be:
  // memcpy(tab2,temp+count1,i2*sizeof(int));
  free(temp);
}

// MergeSort a table of integer of size count.
// Never tested.
void MergeSort(int *tab,int count)
{
  if (count==1) return;

  MergeSort(tab,count/2);
  MergeSort(tab+count/2,(count+1)/2);
  Mix(tab,tab+count/2,count/2,(count+1)/2);
}

 

[edit] 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)		// Rekursive 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;
}

[edit] C#

        public IList MergeSort(IList list)
        {
            if (list.Count <= 1)
                return list;

            int mid = list.Count / 2;

            IList left = new ArrayList();
            IList right = new ArrayList();

            for (int i = 0; i < mid; i++)
                left.Add(list[i]);

            for (int i = mid; i < list.Count; i++)
                right.Add(list[i]);

            return Merge(MergeSort(left), MergeSort(right));
        }

        public IList Merge(IList left, IList right) 
        {
            IList rv = new ArrayList();
            
            while (left.Count > 0 && right.Count > 0)
                if (((IComparable)left[0]).CompareTo(right[0]) > 0)
                {
                    rv.Add(right[0]);
                    right.RemoveAt(0);
                }
                else
                {
                    rv.Add(left[0]);
                    left.RemoveAt(0);
                }

            for (int i = 0; i < left.Count; i++)
                rv.Add(left[i]);

            for (int i = 0; i < right.Count; i++)
                rv.Add(right[i]);

            return rv;
        }

[edit] Common Lisp

;;; Helper function to tell us if a given sequence has just one element.
(defun single (sequence)
  (if (consp sequence)
      (not (cdr sequence))
      (= (length sequence) 1)))

;;; Sequence can be a vector or a list. Note that this means that this
;;; code isn't optimized for any of those.
(defun merge-sort (sequence)
  (if (or (null sequence) (single sequence))
      sequence
      (let ((half (truncate (/ (length sequence) 2))))
        ;; MERGE is a standard common-lisp function, which does just
        ;; what we want.
        (merge (type-of sequence)
               (merge-sort (subseq sequence 0 half))
               (merge-sort (subseq sequence half))
               #'<)))

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

[edit] Erlang

merge_sort(List) when length(List) =< 1 -> List;
merge_sort(List) ->
    {Left, Right} = lists:split(length(List) div 2, List),
    lists:merge(merge_sort(Left), merge_sort(Right)).

[edit] 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(N
   integer, intent(in out) :: C(NC)
 
   integer :: I,J,K
 
   I = 1; J = 1; K = 1;
   do while(I <= NA .and. J <= N
      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

[edit] Groovy

def mergeSort(list){
 if( list.size() <= 1) return list
  center = list.size() / 2
  left  = list[0..center]
  right = list[center..list.size()]
  merge(mergeSort(left), mergeSort(right))
}

def merge(left, right){
  sorted = []
  while(left.size() > 0 || right.size() > 0)
    if(left.get(0) <= right.get(0)){
      sorted << left
    }else{
      sorted << right
    }
  sorted = sorted + left + right
}

[edit] Haskell

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

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

[edit] Java

 public int[] mergeSort(int array[])  {
 	if(array.length > 1)  	{
 		int elementsInA1 = array.length/2;
 		int elementsInA2 = array.length - elementsInA1;
 		int arr1[] = new int[elementsInA1];
 		int arr2[] = new int[elementsInA2];
 		
 		for(int i = 0; i < elementsInA1; i++)
 			arr1[i] = array[i];

 		for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
 			arr2[i - elementsInA1] = array[i];

 		arr1 = mergeSort(arr1);
 		arr2 = mergeSort(arr2);
 		
 		int i = 0, j = 0, k = 0;

 		while(arr1.length != j && arr2.length != k) {
 			if(arr1[j] <= arr2[k]) {
 				array[i] = arr1[j];
 				i++;
 				j++;
 			} else {
 				array[i] = arr2[k];
 				i++;
 				k++;
 			}
 		}

 		while(arr1.length != j) {
 			array[i] = arr1[j];
 			i++;
 			j++;
 		}
 		while(arr2.length != k) {
 			array[i] = arr2[k];
 			i++;
 			k++;
 		}
 	}
 	return array;
 }

[edit] JavaScript

function merge_sort(arr) {
    var l = arr.length, m = Math.floor(l/2);
    if (l <= 1) return arr;
    return merge(merge_sort(arr.slice(0, m)), merge_sort(arr.slice(m)));
}

function merge(left,right) {
    var result = [];
    var ll = left.length, rl = right.length;
    while (ll > 0 && rl > 0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
            ll--;
        } else {
            result.push(right.shift());
            rl--;
        }
    }
    if (ll > 0) {
        result.push.apply(result, left);
    } else if (rl > 0) {
        result.push.apply(result, right);
    }
    return result;
}

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

[edit] OCaml

Function to merge a pair of sorted lists:

# let rec merge = function
    | list, []
    | [], list -> list
    | h1::t1, h2::t2 ->
        if h1 <= h2 then
          h1 :: merge (t1, h2::t2)
        else
          h2 :: merge (h1::t1, t2)
  ;;
val merge : 'a list * 'a list -> 'a list = <fun>

This function is included in the OCaml stdlib as List.merge but is also included here for clarity. Function to halve a list:

# let rec halve = function
    | []
    | [_] as t1 -> t1, []
    | h::t ->
        let t1, t2 = halve t in
          h::t2, t1
  ;;
val halve : 'a list -> 'a list * 'a list = <fun>

Function to merge sort a list:

# let rec merge_sort = function
    | []
    | [_] as list -> list
    | list ->
        let l1, l2 = halve list in
          merge (merge_sort l1, merge_sort l2)
;;
val sort : 'a list -> 'a list = <fun>

For example:

# merge_sort [6; 7; 0; 8; 3; 2; 4; 9; 5; 1];;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

[edit] Opal

Signature:

SIGNATURE Merge[alpha,<]

IMPORT Array[alpha] ONLY array
       Seq   ONLY seq 
       Nat ONLY nat

SORT alpha 
FUN < : alpha ** alpha -> bool

FUN mergeSort:  seq[alpha] -> seq[alpha]

Implementation

IMPLEMENTATION Merge[alpha,<]


IMPORT Array[alpha] COMPLETELY
       Seq          COMPLETELY
       Nat          COMPLETELY
       Bool         COMPLETELY

FUN merge: seq[alpha] ** seq[alpha] -> seq[alpha]
DEF merge((<>, == B
DEF merge(A,(<>) == A
DEF merge(A AS (a::as),B AS (b::bs) ) == IF a < b THEN a::merge(as, ELSE b::merge(A,bs) FI

DEF mergeSort(<> == <>
DEF mergeSort(A AS (a:<>)) == A
DEF mergeSort(lst) == LET 
                        half == #(lst)/2
                        (a,b) == split(half,lst)
                      IN 
                      merge(mergeSort(a),mergeSort(b))

[edit] PHP