RT,归并排序

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5000500;
ll a[N], n;
ll tmp[N]; // 额外的数组
ll k;

void mergesort(ll a[], ll l, ll r ) {
	if ( l >= r )
		return; // 只有 1 个元素
	// step1: 先分治
	ll mid = l + r >> 1;
	mergesort( a, l, mid );
	mergesort( a, mid + 1, r );

	// step2：从最小的区间，开始从左向右比对元素，按条件从左往右进行放置
	ll k = l, i = l, j = mid + 1;
	while ( i <= mid && j <= r )
		if ( a[i] <= a[j] )
			tmp[k++] = a[i++];
		else
			tmp[k++] = a[j++];

	// step3：将剩余已有顺序的元素，直接从左往右直接放置
	while ( i <= mid )
		tmp[k++] = a[i++];
	while ( j <= r )
		tmp[k++] = a[j++];

	// step4：将已排好序的元素，还原到原序列中
	for (i = l; i <= r; i++)
		a[i] = tmp[i];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	mergesort( a, 1, n );

	cout << a[k + 1];
	return 0;
}