```html <مسؤول> <مهمة> <وصف> قم بتنفيذ خوارزمية فرز بالدمج مع قيود على استخدام الذاكرة. </وصف> <متطلبات> <شرط>يجب ألا يتجاوز استخدام الذاكرة الإضافية O(1) في أسوأ الحالات.</شرط> <شرط>يجب أن ت

Kotlin Hard sorting

مهمة «```html <مسؤول> <مهمة> <وصف> قم بتنفيذ خوارزمية فرز بالدمج مع قيود على استخدام الذاكرة. </وصف> <متطلبات> <شرط>يجب ألا يتجاوز استخدام الذاكرة الإضافية O(1) في أسوأ الحالات.</شرط> <شرط>يجب أن ت»

إليك ترجمة النص إلى العربية مع الحفاظ على جميع وسوم HTML وعدم تغيير الأكواد البرمجية:

<p>لديك مصفوفة من الأعداد الصحيحة. يجب ترتيبها تصاعديًا باستخدام ذاكرة إضافية بحجم O(1) فقط (أي بدون استخدام مصفوفات أو قوائم إضافية). يُسمح بتبديل العناصر فقط داخل المصفوفة الأصلية. قم بتنفيذ خوارزمية فرز الدمج في المكان (in-place) باستخدام نهج تكراري من الأسفل إلى الأعلى (bottom-up). اطبع المصفوفة المرتبة مفصولة بمسافات.</p>

تنسيق الإدخال

السطر الأول يحتوي على عدد صحيح N (1 ≤ N ≤ 10^5). السطر الثاني يحتوي على N من الأعداد الصحيحة، مفصولة بمسافات.

تنسيق الإخراج

سطر واحد: N أعداد صحيحة، مرتبة تصاعديًا، مفصولة بمسافات.

أمثلة

مثال 1

الإدخال

1
42

الإخراج

42

مثال 2

الإدخال

6
6 5 4 3 2 1

الإخراج

1 2 3 4 5 6

مثال 3

الإدخال

3.0 4.0

الإخراج

Invalid input

مثال 4

الإدخال

6
4 2 2 8 3 3 1

الإخراج

2 2 3 3 4 8

main.kt