SẮP XẾP MỘT PHẦN MẢNG

Một nhà nghiên cứu dữ liệu đang xử lý một mảng số nguyên gồm nhiều phần tử. Tuy nhiên, thay vì phải sắp xếp toàn bộ mảng, ông chỉ muốn sắp xếp một đoạn con của mảng – cụ thể là các phần tử nằm trong đoạn từ vị trí s đến vị trí t (tính từ 1).

Ngoài ra, người dùng được phép lựa chọn chiều sắp xếp:

• Nếu nhập 1, đoạn mảng được sắp xếp tăng dần.

• Nếu nhập 0, đoạn mảng được sắp xếp giảm dần.

Các phần tử nằm ngoài đoạn [s, t] phải giữ nguyên vị trí ban đầu.

Yêu cầu: Sử dụng thuật toán Sắp xếp trộn để giải quyết bài toán.

📥 Dữ liệu vào:

• Dòng 1: Một số nguyên n — số phần tử của mảng (1 ≤ n ≤ 10⁵).

• Dòng 2: n số nguyên — các phần tử của mảng.

• Dòng 3: Ba số nguyên s, t, c — trong đó:

  • s, t là hai chỉ số (1 ≤ s ≤ t ≤ n),

  • c là hướng sắp xếp (1: tăng dần, 0: giảm dần).

📤 Dữ liệu ra:

• Một dòng gồm n số nguyên — mảng sau khi sắp xếp theo yêu cầu.

Ví dụ: