Sort an Array - Practice Coding Problems

Sort an Array - Problem

Array Divide and Conquer Sorting Heap (Priority Queue) Merge Sort Bucket Sort Radix Sort Counting Sort Medium

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

You must solve the problem without using any built-in functions in O(n log n) time complexity and with the smallest space complexity possible.

Input & Output

Example 1 — Basic Sorting

$ Input: nums = [5,2,8,6,1,9,4]

› Output: [1,2,4,5,6,8,9]

💡 Note: Sort the array in ascending order: all elements arranged from smallest to largest

Example 2 — Already Sorted

$ Input: nums = [1,2,3,4,5]

› Output: [1,2,3,4,5]

💡 Note: Array is already sorted, return as is

Example 3 — Reverse Order

$ Input: nums = [5,4,3,2,1]

› Output: [1,2,3,4,5]

💡 Note: Array in reverse order, needs complete reordering to ascending

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
-5 × 10⁴ ≤ nums[i] ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted array of integers

Process

Apply sorting algorithm (merge sort, heap sort, etc.)

Output

Array sorted in ascending order

Key Takeaway

🎯 Key Insight: Use divide-and-conquer algorithms like merge sort to achieve optimal O(n log n) time complexity

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Facebook 6

The key insight is to use divide-and-conquer algorithms like merge sort or heap sort to achieve O(n log n) time complexity. Merge sort is optimal for stability and predictable performance, while heap sort achieves optimal O(1) space complexity. Time: O(n log n), Space: O(1) with heap sort or O(n) with merge sort.

Common Approaches

Approach	Time	Space	Notes
✓ Bubble Sort (Brute Force)	O(n²)	O(1)	Repeatedly swap adjacent elements if they are in wrong order
Merge Sort	O(n log n)	O(n)	Divide array into halves, sort recursively, then merge sorted halves
Heap Sort	O(n log n)	O(1)	Build max heap, then repeatedly extract maximum to get sorted order

Bubble Sort (Brute Force) — Algorithm Steps

Step 1: Compare adjacent elements
Step 2: Swap if left > right
Step 3: Repeat until no swaps needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Adjacent

Compare each pair of adjacent elements

Swap if Needed

Swap if left element is greater than right

Repeat

Continue until no swaps are needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        int swapped = 0;
        for (int j = 0; j < numsSize - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    solution(nums, size);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", nums[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops - outer loop runs n times, inner loop runs up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables for swapping, no extra arrays

✓ Linear Space

85.0K Views

High Frequency

~15 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bubble Sort (Brute Force) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler