[ تعرٌف على ] تصنيف دمجي

تم النشر اليوم 06-12-2025 | [ تعرٌف على ] تصنيف دمجي
تم النشر اليوم [dadate] | تصنيف دمجي

تطبيق من الأعلى إلى الأسفل (Top-down)

function merge_sort(list m) // if list size is 1, consider it sorted and return it if length(m) <= 1 return m // else list size is > 1, so split the list into two sublists var list left, right var integer middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after or equal middle add x to right // recursively call merge_sort() to further split each sublist // until sublist size is 1 left = merge_sort(left) right = merge_sort(right) // merge the sublists returned from prior calls to merge_sort() // and return the resulting merged sublist return merge(left, right) في هذا المثال، الدالة merge تدمج المجموعتين الجزئيتين اليسرى واليمنى: function merge(left, right) var list result while length(left) > 0 or length(right) > 0 if 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) else if length(left) > 0 append first(left) to result left = rest(left) else if length(right) > 0 append first(right) to result right = rest(right) end while return result

تطبيق من الأسفل إلى الأعلى (Bottom-up)

/* array A[] has the items to sort; array B[] is a work array */ BottomUpSort(int n, array A[n], array B[n]) { int width; /* each 1-element run in A is already "sorted". */ /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted */ for (width = 1; width < n; width = 2 * width) { int i; /* array A is full of runs of length width */ for (i = 0; i < n; i = i + 2 * width) { /* merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */ /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */ BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B); } /* now work array B is full of runs of length 2*width */ /* copy array B to array A for next iteration */ /* a more efficient implementation would swap the roles of A and B */ CopyArray(A, B, n); /* now array A is full of runs of length 2*width */ } } BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[]) { int i0 = iLeft; int i1 = iRight; int j; /* while there are elements in the left or right lists */ for (j = iLeft; j < iEnd; j++) { /* if left list head exists and is <= existing right list head */ if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1])) { B[j] = A[i0]; i0 = i0 + 1; } else { B[j] = A[i1]; i1 = i1 + 1; } } }

شرح مبسط

تعديل - تعديل مصدري - تعديل ويكي بيانات