Sort an Array

Problem

Given an array of integers nums, sort the array in ascending order and return it.

Examples

The brute-force approach

Selection sort or insertion sort: O(n²). Simple to implement but fails the time constraint.

for i in range(n):
    for j in range(i+1, n):
        if nums[j] < nums[i]:
            nums[i], nums[j] = nums[j], nums[i]

O(n²) comparisons — too slow for large inputs.

Spotting the pattern

This is a Sorting Algorithms problem. The key question to ask yourself:

After sorting the left and right halves independently, how do you combine them into a single sorted array?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.