Sort an Array

Java coding interview problem for Array Coding: Sort an Array.

Sorting an array is one of the most important concepts in Data Structures and Algorithms.

Sorting means arranging elements in a specific order.

Usually:

Ascending order
Descending order

Sorting is the foundation of many advanced algorithms:

Binary Search
Two Pointer Problems
Interval Problems
Greedy Algorithms
Database Query Optimization
Data Analysis

What Does Sorting an Array Mean?

Sorting rearranges elements based on their values.

Example:

Input:

[50, 20, 40, 10, 30]

Ascending order:

[10,20,30,40,50]

Descending order:

[50,40,30,20,10]

Types of Sorting

1. Ascending Order

Smallest value comes first.

Example:

1,2,3,4,5

2. Descending Order

Largest value comes first.

Example:

5,4,3,2,1

Why is Sorting Important in Interviews?

Sorting problems are frequently asked because they test:

Algorithm knowledge
Time complexity understanding
Problem-solving skills
Optimization techniques

Many interview problems become easier after sorting.

Example:

Without sorting:

Find duplicate values

may require extra memory.

After sorting:

[1,2,2,3]

Duplicates become adjacent.

Real-World Applications

Sorting is used in almost every software system.

E-Commerce Applications

Products sorted by:

Price
Rating
Popularity
Reviews

Example:

Before sorting:

Laptop A  $900

Laptop B  $700

Laptop C  $1200

Sort by price:

Laptop B  $700

Laptop A  $900

Laptop C  $1200

Banking Systems

Transactions sorted by:

Date
Amount
Account activity

Example:

Latest transactions first

Search Engines

Search results are ranked by:

Relevance
Popularity
Date

Data Analytics

Reports sort data by:

Highest revenue
Lowest cost
Performance

Operating Systems

Processes may be sorted by:

Priority
Execution time
Resource usage

Problem Statement

Given an integer array,

sort the elements in ascending order.

Example 1

Input:

[5,2,8,1,3]

Output:

[1,2,3,5,8]

Example 2

Input:

[10,5,10,2]

Output:

[2,5,10,10]

Example 3

Input:

[-5,3,-1,8]

Output:

[-5,-1,3,8]

Understanding Sorting

Consider:

[7,4,9,2,5]

Goal:

Move smaller elements to the left.

After first pass:

[2,4,7,9,5]

After second pass:

[2,4,5,7,9]

Final:

[2,4,5,7,9]

Sorting Visualization

Input:

[8,3,5,1,9]

Compare:

8 > 3

Swap:

[3,8,5,1,9]

Compare:

8 > 5

Swap:

[3,5,8,1,9]

Compare:

8 > 1

Swap:

[3,5,1,8,9]

Continue until sorted.

Sorting Algorithm Categories

Sorting algorithms can be divided into:

Comparison Based Sorting

Elements are compared.

Examples:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

Non-Comparison Sorting

Uses other techniques.

Examples:

Counting Sort
Radix Sort
Bucket Sort

Dry Run

Input:

[6,4,2,8,1]

Pass 1:

Compare:

6 and 4

Swap:

[4,6,2,8,1]

Compare:

6 and 2

Swap:

[4,2,6,8,1]

Compare:

6 and 8

No swap.

Compare:

8 and 1

Swap:

[4,2,6,1,8]

Largest element reaches end.

Approach 1 — Using Java Built-in Sorting (Recommended)

Java provides built-in sorting methods through:

Arrays.sort()

This is the recommended approach for production applications.

Algorithm

Import java.util.Arrays.
Call:

Arrays.sort(array);

Array becomes sorted.

Java Program

import java.util.Arrays;

public class SortArrayUsingArraysSort {

    public static void main(String[] args) {

        int[] numbers =
                {5,2,8,1,3};

        Arrays.sort(numbers);

        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,2,3,5,8]

Step-by-Step Explanation

Original array:

[5,2,8,1,3]

Call:

Arrays.sort(numbers);

Java internally sorts the array.

After sorting:

[1,2,3,5,8]

Print:

Arrays.toString(numbers)

Sorting in Descending Order

For primitive arrays:

int[]

we cannot directly use a comparator.

Use wrapper type:

Integer[]

Java Program

import java.util.Arrays;
import java.util.Collections;

public class SortDescending {

    public static void main(String[] args) {

        Integer[] numbers =
                {5,2,8,1,3};


        Arrays.sort(
                numbers,
                Collections.reverseOrder());


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[8,5,3,2,1]

Internal Working of Arrays.sort()

For primitive arrays:

Java uses:

Dual-Pivot QuickSort

Characteristics:

Fast average performance
In-place sorting
Good cache performance

Average complexity:

O(n log n)

For Object arrays:

Java uses:

TimSort

Characteristics:

Stable sorting
Hybrid merge sort
Efficient for partially sorted data

Complexity Analysis

For primitive arrays:

Operation	Complexity
Average Time	O(n log n)
Worst Time	O(n²)
Space	O(log n)

For Object arrays:

Operation	Complexity
Average Time	O(n log n)
Worst Time	O(n log n)
Space	O(n)

Advantages

Production-ready.
Highly optimized.
Less code.
Handles large arrays efficiently.
Maintained by Java experts.

Drawbacks

Internal implementation knowledge is hidden.
Not useful for learning sorting algorithms.
Modifies original array.

Approach 2 — Bubble Sort (Beginner Understanding)

Bubble Sort is one of the simplest sorting algorithms.

The idea:

Compare adjacent elements.

If the left element is greater:

Swap them.

Example

Input:

[5,3,8,1]

Compare:

5 > 3

Swap:

[3,5,8,1]

Continue:

8 > 1

Swap:

[3,5,1,8]

Largest value moves to the end.

This process is called:

Bubble

because larger elements "bubble" toward the end.

Algorithm

Run multiple passes.
Compare adjacent elements.
Swap if incorrect order.
Repeat until sorted.

Java Program

import java.util.Arrays;

public class BubbleSort {

    public static void sort(int[] numbers) {

        int n = numbers.length;


        for(int i = 0; i < n - 1; i++) {

            for(int j = 0; j < n - i - 1; j++) {

                if(numbers[j] > numbers[j + 1]) {

                    int temp = numbers[j];

                    numbers[j] = numbers[j + 1];

                    numbers[j + 1] = temp;

                }

            }

        }

    }


    public static void main(String[] args) {

        int[] numbers =
                {5,2,8,1,3};


        sort(numbers);


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,2,3,5,8]

Step-by-Step Explanation

Pass 1:

[5,2,8,1,3]

Compare:

5 and 2

Swap:

[2,5,8,1,3]

Compare:

8 and 1

Swap:

[2,5,1,8,3]

After several swaps:

Largest value reaches end.

Complexity Analysis

Worst:

O(n²)

Average:

O(n²)

Best:

O(n)

(with optimization)

Space:

O(1)

Advantages

Very easy to understand.
Good for learning sorting concepts.
In-place algorithm.

Drawbacks

Very slow for large data.
Not used in production.
Too many comparisons.

Approach 2 (Optimized) — Bubble Sort with Early Termination

The basic Bubble Sort always performs all comparisons even if the array is already sorted.

We can optimize it by checking whether any swaps happened during a pass.

If no swaps occur:

Array is already sorted

We can stop immediately.

Algorithm

Run multiple passes.
Compare adjacent elements.
Swap if left element is greater.
Track whether any swap happened.
If no swap happens, stop.

Java Program

import java.util.Arrays;

public class OptimizedBubbleSort {

    public static void sort(int[] numbers) {

        int n = numbers.length;


        for (int i = 0; i < n - 1; i++) {

            boolean swapped = false;


            for (int j = 0; j < n - i - 1; j++) {

                if (numbers[j] > numbers[j + 1]) {

                    int temp = numbers[j];

                    numbers[j] = numbers[j + 1];

                    numbers[j + 1] = temp;


                    swapped = true;

                }

            }


            if (!swapped) {

                break;

            }

        }

    }


    public static void main(String[] args) {

        int[] numbers =
                {5,2,8,1,3};


        sort(numbers);


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,2,3,5,8]

Complexity Analysis

Case	Time Complexity
Best Case	O(n)
Average Case	O(n²)
Worst Case	O(n²)

Space:

O(1)

Approach 3 — Selection Sort

Selection Sort works by repeatedly finding the smallest element and placing it at the correct position.

Example

Input:

[5,3,8,1,2]

Find minimum:

Swap with first element:

[1,3,8,5,2]

Next minimum:

Swap:

[1,2,8,5,3]

Continue until sorted.

Algorithm

Divide array into:
- Sorted part
- Unsorted part
Find minimum element from unsorted section.
Swap it with first unsorted position.
Repeat.

Java Program

import java.util.Arrays;

public class SelectionSort {

    public static void sort(int[] numbers) {

        int n = numbers.length;


        for (int i = 0; i < n - 1; i++) {

            int minimumIndex = i;


            for (int j = i + 1; j < n; j++) {

                if (numbers[j] < numbers[minimumIndex]) {

                    minimumIndex = j;

                }

            }


            int temp = numbers[i];

            numbers[i] = numbers[minimumIndex];

            numbers[minimumIndex] = temp;

        }

    }


    public static void main(String[] args) {

        int[] numbers =
                {5,3,8,1,2};


        sort(numbers);


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,2,3,5,8]

Complexity Analysis

Time:

O(n²)

Space:

O(1)

Advantages

Easy to understand.
Performs fewer swaps than Bubble Sort.
In-place sorting.

Drawbacks

Slow for large arrays.
Always performs O(n²) comparisons.

Approach 4 — Insertion Sort

Insertion Sort builds the sorted array one element at a time.

It works similar to arranging playing cards.

Example

Input:

[5,3,8,1]

Start:

[5]

Insert:

Result:

[3,5]

Insert:

Result:

[3,5,8]

Insert:

Result:

[1,3,5,8]

Algorithm

Assume first element is sorted.
Pick next element.
Compare with sorted elements.
Shift larger elements.
Insert element at correct position.

Java Program

import java.util.Arrays;

public class InsertionSort {

    public static void sort(int[] numbers) {

        int n = numbers.length;


        for (int i = 1; i < n; i++) {

            int current = numbers[i];

            int j = i - 1;


            while (j >= 0 &&
                    numbers[j] > current) {

                numbers[j + 1] = numbers[j];

                j--;

            }


            numbers[j + 1] = current;

        }

    }


    public static void main(String[] args) {

        int[] numbers =
                {5,3,8,1,2};


        sort(numbers);


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,2,3,5,8]

Complexity Analysis

Case	Time
Best	O(n)
Average	O(n²)
Worst	O(n²)

Space:

O(1)

Advantages

Efficient for small arrays.
Excellent for nearly sorted data.
Stable sorting algorithm.

Drawbacks

Slow for large random arrays.

Approach 5 — Merge Sort

Merge Sort uses the Divide and Conquer technique.

It:

Divides array into halves.
Sorts each half.
Merges sorted halves.

Visualization

Input:

[8,3,5,1]

Divide:

[8,3]

[5,1]

Divide again:

[8]

[3]

[5]

[1]

Merge:

[3,8]

[1,5]

Final merge:

[1,3,5,8]

Java Program

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(
            int[] numbers,
            int left,
            int right) {


        if (left < right) {

            int mid =
                    (left + right) / 2;


            mergeSort(
                    numbers,
                    left,
                    mid);


            mergeSort(
                    numbers,
                    mid + 1,
                    right);


            merge(
                    numbers,
                    left,
                    mid,
                    right);

        }

    }


    private static void merge(
            int[] numbers,
            int left,
            int mid,
            int right) {


        int[] temp =
                new int[right - left + 1];


        int i = left;

        int j = mid + 1;

        int k = 0;


        while (i <= mid &&
                j <= right) {


            if (numbers[i] <= numbers[j]) {

                temp[k++] = numbers[i++];

            } else {

                temp[k++] = numbers[j++];

            }

        }


        while (i <= mid) {

            temp[k++] = numbers[i++];

        }


        while (j <= right) {

            temp[k++] = numbers[j++];

        }


        for (int x = 0; x < temp.length; x++) {

            numbers[left + x] = temp[x];

        }

    }


    public static void main(String[] args) {

        int[] numbers =
                {8,3,5,1};


        mergeSort(
                numbers,
                0,
                numbers.length - 1);


        System.out.println(
                Arrays.toString(numbers));

    }

}

Output

[1,3,5,8]

Complexity Analysis

Time:

O(n log n)

Space:

O(n)

Advantages

Guaranteed O(n log n).
Stable sorting.
Good for large datasets.

Drawbacks

Requires extra memory.
More complex implementation.

Approach 6 — Quick Sort

Quick Sort also uses divide and conquer.

Steps:

Select pivot.
Place smaller values left.
Place larger values right.
Recursively sort partitions.

Example

Input:

[8,3,5,1,9]

Pivot:

Partition:

[3,1] 5 [8,9]

Sort parts:

[1,3,5,8,9]

Complexity

Average:

O(n log n)

Worst:

O(n²)

Space:

O(log n)

Stable vs Unstable Sorting

Stable Sorting

Maintains relative order of equal elements.

Examples:

Merge Sort
Insertion Sort
TimSort

Unstable Sorting

Equal elements may change order.

Examples:

Quick Sort
Selection Sort
Heap Sort

Primitive vs Object Array Sorting

Primitive Arrays

Example:

int[]

Uses:

Dual Pivot QuickSort

Object Arrays

Example:

Integer[]

Uses:

TimSort

Benefits:

Stable sorting.
Handles partially sorted data efficiently.

Java Streams Sorting

Example:

Arrays.stream(numbers)
      .sorted()
      .toArray();

Descending Order

Arrays.stream(numbers)
      .boxed()
      .sorted((a,b) -> b-a)
      .toArray(Integer[]::new);

Complete Sorting Comparison

Algorithm	Best	Average	Worst	Space	Stable
Arrays.sort()	O(n log n)	O(n log n)	O(n log n)	O(log n)	Depends
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No

Common Interview Mistakes

Mistake 1

Using Bubble Sort for production code.

Use:

Arrays.sort()

instead.

Mistake 2

Not understanding stability.

Stable sorting matters when sorting objects.

Mistake 3

Ignoring descending order requirements.

Mistake 4

Using comparator incorrectly.

Avoid:

b - a

for extreme values.

Prefer:

Integer.compare(b,a)

Mistake 5

Forgetting primitive arrays cannot use Comparator.

Edge Cases

Input	Output
`[]`	`[]`
`[1]`	`[1]`
`[5,5,5]`	`[5,5,5]`
Negative numbers	Works
Already sorted array	Same array

Interview Follow-up Questions

Q1. Which sorting algorithm does Java use?

Q2. Difference between Quick Sort and Merge Sort?

Q3. What is stable sorting?

Q4. Sort without using built-in methods.

Q5. Sort an almost sorted array.

Q6. Find Kth smallest after sorting.

Q7. Sort an array of objects.

Q8. Why is Arrays.sort() faster?

Key Takeaways

Sorting is a foundation of many algorithms.
Use Arrays.sort() for production applications.
Learn Bubble, Selection, and Insertion Sort for fundamentals.
Learn Merge and Quick Sort for interviews.
Understand:
- Time complexity
- Space complexity
- Stability
- Internal implementation

Interview Tip

When asked:

"Sort an array."

First clarify:

Can built-in sorting be used?
Is this a learning algorithm question?
Are memory constraints involved?

For production:

Arrays.sort()

For interviews:

Explain:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

Then discuss trade-offs:

Speed
Memory
Stability
Input characteristics

A strong explanation of sorting algorithms demonstrates both Java expertise and algorithmic thinking.