JavaScript Coding Test Course, Sorting Numbers 1

Problem Description

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.

Input

The first line contains the number of integers N (1 ≤ N ≤ 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.

Output

Print the sorted numbers in ascending order, one per line, starting from the first line.

Problem Solving Process

Step 1: Problem Analysis

To understand the given problem, we need to clarify the structure of the input data and the required output.
– Input: Number N and the next N integers
– Output: The N integers sorted in non-decreasing order

The key to the problem is using an efficient sorting algorithm.
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.).
Therefore, we need to use sorting algorithms with a complexity of O(N log N), such as quicksort or mergesort.

Step 2: Algorithm Selection

We can use the built-in method of JavaScript Array.prototype.sort(), but since we need to guarantee the stability of the sort, we will implement quicksort or mergesort.

Step 3: Implementation

I will solve the problem using the Merge Sort algorithm.
Merge Sort works by dividing the list in half, recursively sorting each part, and then merging the two sorted parts.

Execution Process of Merge Sort

• Divide the array into two subarrays by splitting it in half.
• Recursively sort each subarray.
• Combine the two sorted subarrays to create one sorted array.

Implementation of Merge Sort

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0; 
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}
    

Step 4: Input and Output Processing

Now, I will write a function that takes input, sorts it using merge sort, and then outputs the results.
I will read the nodes, convert them to an array, and then call the merge sort function.

const fs = require('fs');

// Read input from the file.
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const n = input.shift(); // Remove the first line which indicates the number of integers.

const sortedArray = mergeSort(input);

console.log(sortedArray.join('\\n')); // Print the sorted result with line breaks.
    

Step 5: Testing and Result Verification

I have tested the implemented code using the sample input.
Using the following input:

5
5
2
3
1
4
    

The expected output is as follows.

1
2
3
4
5
    

Conclusion

Through this problem, I learned about the importance of sorting algorithms in JavaScript and how to implement Merge Sort.
Since this is a common topic in practical interviews and coding tests, it is important to practice and implement various cases.
Understanding the theory of algorithms, along with writing code to get hands-on experience, is a crucial method for improving skills.