\n Write a program to sort N given numbers in non-decreasing order. Non-decreasing order means that in the sorted sequence, a number can be equal to or greater than the preceding number.\n <\/p>\n
\n The first line contains the number of integers N (1 \u2264 N \u2264 1,000,000). From the second line, N lines follow, each containing one integer. Each integer is a whole number and its absolute value does not exceed 1,000,000.\n <\/p>\n
\n Print the sorted numbers in ascending order, one per line, starting from the first line.\n <\/p>\n
Output Example:<\/strong> \n To understand the given problem, we need to clarify the structure of the input data and the required output. \n The key to the problem is using an efficient sorting algorithm. \n We can use the built-in method of JavaScript \n I will solve the problem using the Merge Sort algorithm. \n Now, I will write a function that takes input, sorts it using merge sort, and then outputs the results. \n I have tested the implemented code using the sample input. \n The expected output is as follows.\n <\/p>\n \n Through this problem, I learned about the importance of sorting algorithms in JavaScript and how to implement Merge Sort.
\n 1
\n 2
\n 3
\n 4
\n 5\n <\/div>\nProblem Solving Process<\/h2>\n
Step 1: Problem Analysis<\/h3>\n
\n – Input: Number N and the next N integers
\n – Output: The N integers sorted in non-decreasing order\n <\/p>\n
\n Since the size of the array can be up to 1,000,000, we cannot use common O(N^2) algorithms (like bubble sort, selection sort, etc.).
\n Therefore, we need to use sorting algorithms with a complexity of O(N log N), such as quicksort or mergesort.\n <\/p>\nStep 2: Algorithm Selection<\/h3>\n
Array.prototype.sort()<\/code>, but since we need to guarantee the stability of the sort, we will implement quicksort or mergesort.\n <\/p>\nStep 3: Implementation<\/h3>\n
\n Merge Sort works by dividing the list in half, recursively sorting each part, and then merging the two sorted parts.\n <\/p>\nExecution Process of Merge Sort<\/h4>\n
\n
Implementation of Merge Sort<\/h4>\n
\nfunction mergeSort(arr) {\n if (arr.length <= 1) {\n return arr;\n }\n\n const mid = Math.floor(arr.length \/ 2);\n const left = mergeSort(arr.slice(0, mid));\n const right = mergeSort(arr.slice(mid));\n\n return merge(left, right);\n}\n\nfunction merge(left, right) {\n const result = [];\n let i = 0; \n let j = 0;\n\n while (i < left.length && j < right.length) {\n if (left[i] < right[j]) {\n result.push(left[i]);\n i++;\n } else {\n result.push(right[j]);\n j++;\n }\n }\n\n return result.concat(left.slice(i)).concat(right.slice(j));\n}\n <\/code><\/pre>\nStep 4: Input and Output Processing<\/h3>\n
\n I will read the nodes, convert them to an array, and then call the merge sort function.\n <\/p>\n\nconst fs = require('fs');\n\n\/\/ Read input from the file.\nlet input = fs.readFileSync('\/dev\/stdin').toString().trim().split('\\n').map(Number);\nconst n = input.shift(); \/\/ Remove the first line which indicates the number of integers.\n\nconst sortedArray = mergeSort(input);\n\nconsole.log(sortedArray.join('\\\\n')); \/\/ Print the sorted result with line breaks.\n <\/code><\/pre>\nStep 5: Testing and Result Verification<\/h3>\n
\n Using the following input:\n <\/p>\n\n5\n5\n2\n3\n1\n4\n <\/code><\/pre>\n\n1\n2\n3\n4\n5\n <\/code><\/pre>\nConclusion<\/h2>\n
\n Since this is a common topic in practical interviews and coding tests, it is important to practice and implement various cases.
\n Understanding the theory of algorithms, along with writing code to get hands-on experience, is a crucial method for improving skills.\n <\/p>\n