Merge sort run cố định

anh mới nghe từ run(chạy) cố định và run(chạy) tự nhiên.
không hiểu là gì luôn.
em lấy thông tin này ở đâu ra vậy.

đề lập trình của thầy em.
chính xát là đề nó thế này
3. Cài đặt mergesort theo run cố định (cách 2)
4*. Cài đặt mergesort theo run tự nhiên (cách 3)

hic hic, thuật toán về merger sort anh bỏ lâu rồi.
Nên giờ không biết gì luôn.
không hiểu run cố định là sao luôn.
Em có thể tham khảo link

Sắp xếp trộn

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948. Giả sử có hai danh sách đã được sắp xếp ...

Em cảm ơn anh !
Dạ em củng coi qua cái đó rồi
Không biết nó có phải là cái Trộn tại chỗ không ?

Em đã tìm ra lời giải

#include "stdafx.h"
#include <iostream>
#include "math.h"
#define MAX 15
using namespace std;
// trả về số nhỏ hơn
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

// trộn 2 dãy phụ tạo dãy mới
void Tron(int a[], int temp1[], int n1, int temp2[], int n2, int k)
{
	int i1, i2, i;
	int k1, k2;
	int j1, j2;
	i = i1 = i2 = 0;
	j1 = j2 = 0;

	while (n2 > 0 && n2 > 0)
	{
		// xác định độ dài từng dãy con 2 dãy phụ
		k1 = min(k, n1);
		k2 = min(k, n2);

		// xét và trộn dãy con vào dãy
		if (temp1[i1 + j1] < temp2[i2 + j2])
		{
			a[i++] = temp1[i1 + j1];
			j1++;

			// trộn dãy con còn lại vào dãy
			if (j1 == k1)
			{
				for (; j2 < k2; j2++)
					a[i++] = temp2[i2 + j2];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
		else
		{
			a[i++] = temp2[i2 + j2];
			j2++;

			// trộn dãy con còn lại vào dãy
			if (j2 == k2)
			{
				for (; j1 < k1; j1++)
					a[i++] = temp1[i1 + j1];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
	}
}

void MergeSort(int a[], int n)
{
	int n1, n2;
	int i;
	int k;
	int ik;
	int temp1[MAX], temp2[MAX];
	k = 1;

	do
	{
		i = n1 = n2 = 0;

		// chia mảng ra 2 mảng phụ
		while (i < n)
		{
			ik = 0;

			while (ik < k && i < n)
			{
				temp1[n1++] = a[i++];
				ik++;
			}

			ik = 0;

			while (ik < k && i < n)
			{
				temp2[n2++] = a[i++];
				ik++;
			}
		}

		Tron(a, temp1, n1, temp2, n2, k);

		// tăng độ lớn tối đa dãy con
		k *= 2;
	} while (k < n);

}

void main()
{
	int n = 15;
	int a[MAX] = { 10,3,4,14,9,7,12,11,8,5,2,1,13,15,6 };
	cout << "Mang a " << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	cout << "Mang a sau khi sap xep bang MergeSort co dinh " << endl;
	MergeSort(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

}