Sorting Arrays: Techniques and Algorithms

What Is Array Sorting?

Array sorting is the process of arranging the elements of an array according to a defined order. The order may be ascending, descending, alphabetical, or based on a custom comparison rule.

Sorting is an important operation in data structures because ordered data can make other operations easier to perform. For example, a sorted array can be searched using binary search, while ordered data can make reporting, ranking, and range-based operations more convenient.

Example of Sorting an Array

Consider an unsorted array:

[42, 15, 73, 8, 31]

Sorting the values in ascending order produces:

[8, 15, 31, 42, 73]

In descending order, the same values become:

[73, 42, 31, 15, 8]

Why Is Array Sorting Important?

Sorting is often used as a preparation step for other algorithms and application features. Once data is ordered, some operations can be performed more systematically or efficiently.

• Enabling efficient searching techniques such as binary search.
• Displaying records in a meaningful order.
• Finding minimum and maximum values easily.
• Grouping related values together.
• Preparing data for merging and other algorithms.
• Generating rankings and ordered reports.
• Supporting range-based processing.

Ascending and Descending Order

The two most common sorting orders are ascending and descending.

Common Array Sorting Algorithms

Different sorting algorithms use different strategies to arrange array elements. Common algorithms studied in data structures include:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort

These algorithms differ in their time complexity, memory usage, stability, and implementation characteristics.

Bubble Sort

Bubble Sort repeatedly compares neighboring elements and swaps them when they are in the wrong order. Larger values gradually move toward the end of the array during each pass.

[5, 2, 8, 1]

Compare 5 and 2:
[2, 5, 8, 1]

Compare 5 and 8:
[2, 5, 8, 1]

Compare 8 and 1:
[2, 5, 1, 8]

Bubble Sort is easy to understand but generally inefficient for large collections.

Selection Sort

Selection Sort repeatedly finds the smallest element from the unsorted portion and places it at the next sorted position.

[29, 10, 14, 37, 13]

Smallest = 10

[10, 29, 14, 37, 13]

Next smallest = 13

[10, 13, 14, 37, 29]

Selection Sort performs O(n²) comparisons in its typical implementation, regardless of whether the input is already nearly sorted.

Insertion Sort

Insertion Sort builds the sorted portion of an array one element at a time. Each new element is inserted into its appropriate position among the elements that have already been sorted.

[5, 2, 4, 6]

Start:
[5]

Insert 2:
[2, 5]

Insert 4:
[2, 4, 5]

Insert 6:
[2, 4, 5, 6]

Insertion Sort can perform well on small or nearly sorted arrays and is also commonly used as part of hybrid sorting strategies.

Merge Sort

Merge Sort uses a divide-and-conquer strategy. It repeatedly divides the array into smaller portions, sorts those portions, and then merges them into a sorted result.

[38, 27, 43, 3]

Divide:

[38, 27]   [43, 3]

Divide again:

[38] [27]   [43] [3]

Sort and merge:

[27, 38]   [3, 43]

Final:

[3, 27, 38, 43]

Merge Sort has O(n log n) time complexity and provides predictable performance for large inputs. The standard array implementation requires additional memory for merging.

Quick Sort

Quick Sort selects a pivot and partitions the array so that values are placed on the appropriate side of the pivot. The resulting portions are then sorted recursively.

[7, 2, 9, 4, 5]

Choose pivot = 5

Smaller values:
[2, 4]

Pivot:
[5]

Larger values:
[7, 9]

Sort both sides:

[2, 4, 5, 7, 9]

Quick Sort has an average time complexity of O(n log n), but a poorly chosen pivot can produce O(n²) worst-case behavior in some implementations.

Heap Sort

Heap Sort uses a heap data structure to repeatedly select the next element that belongs in the sorted order.

Heap Sort provides O(n log n) worst-case time complexity and can be implemented in-place, although it is generally not stable.

Sorting Algorithm Complexity

Understanding time complexity is important when selecting a sorting algorithm for a particular workload.

* Bubble Sort can achieve O(n) best-case time when the implementation detects that no swaps are required during a pass.

What Is a Stable Sorting Algorithm?

A stable sorting algorithm preserves the relative order of elements that have equal sorting keys.

For example, consider records containing a name and score:

[
  { name: "Asha", score: 80 },
  { name: "Ravi", score: 70 },
  { name: "Maya", score: 80 }
]

If the records are sorted by score and the sorting algorithm is stable, Asha remains before Maya because they originally appeared in that order and have the same score.

Stable vs Unstable Sorting

Stability becomes important when sorting records using multiple criteria. A stable sort can preserve the ordering established by an earlier sort when the current sorting key is equal.

Stability can depend on the specific implementation, so the table describes common implementations rather than an absolute property of every implementation.

What Does In-Place Sorting Mean?

An in-place sorting algorithm rearranges the elements using a relatively small amount of additional memory rather than creating a completely separate array for the sorted result.

In-place sorting can be useful when memory usage is an important consideration, although the exact auxiliary space depends on the implementation.

Sorting Numbers in JavaScript

JavaScript arrays provide the sort() method. When sorting numbers, a comparison function should normally be supplied because the default behavior sorts values as strings.

const numbers = [40, 5, 100, 25];

numbers.sort((a, b) => a - b);

console.log(numbers);
// [5, 25, 40, 100]

Why Does JavaScript Need a Comparison Function?

Without a comparison function, JavaScript's sort() method compares array elements according to string ordering.

const numbers = [10, 2, 30, 4];

numbers.sort();

console.log(numbers);
// [10, 2, 30, 4]

numbers.sort((a, b) => a - b);

console.log(numbers);
// [2, 4, 10, 30]

The expression a - b tells the comparison function to place smaller numeric values before larger ones.

Sorting in Descending Order With JavaScript

To sort numbers from largest to smallest, reverse the comparison:

const numbers = [40, 5, 100, 25];

numbers.sort((a, b) => b - a);

console.log(numbers);
// [100, 40, 25, 5]

Sorting an Array of Objects

Real applications commonly sort objects using one of their properties. The comparison function can define which property determines the order.

const products = [
  { name: "Keyboard", price: 50 },
  { name: "Mouse", price: 25 },
  { name: "Monitor", price: 180 }
];

products.sort((a, b) => a.price - b.price);

console.log(products);

Sorting Strings in JavaScript

Strings can be sorted using sort(). For more predictable locale-aware ordering, localeCompare() can be used.

const names = ["Maya", "Asha", "Ravi", "John"];

names.sort((a, b) => a.localeCompare(b));

console.log(names);
// ["Asha", "John", "Maya", "Ravi"]

Sorting Before Binary Search

Sorting and searching are closely related operations. Binary search can efficiently search an appropriately sorted array, but an unsorted array must first be sorted if binary search is to be used on that ordering.

const numbers = [50, 10, 40, 20, 30];

numbers.sort((a, b) => a - b);

console.log(numbers);
// [10, 20, 30, 40, 50]

// Binary search can now use the sorted ordering.

When deciding whether sorting is worthwhile, consider how many searches will follow and whether the data changes frequently. Sorting introduces its own cost, so the complete workload should be considered.

Sorting vs Searching

Sorting and searching solve different problems but are often used together.

How to Choose a Sorting Algorithm

Choosing a sorting algorithm depends on more than its worst-case time complexity. The size of the collection, whether the data is already partially sorted, memory constraints, stability requirements, and the implementation environment can all matter.

• Use simple algorithms such as insertion sort when the data is small or nearly sorted.
• Consider O(n log n) algorithms for larger collections.
• Consider stability when sorting records with equal keys.
• Consider auxiliary memory when working with memory-sensitive workloads.
• Consider whether the data is already sorted or changes frequently.

Common Array Sorting Mistakes

• Forgetting that JavaScript's default numeric sorting behavior is not numeric ascending order.
• Using a sorting algorithm without considering its worst-case complexity.
• Assuming every sorting algorithm is stable.
• Ignoring additional memory requirements.
• Sorting data unnecessarily when it will only be used once.
• Using binary search without first ensuring the required ordering exists.
• Comparing objects without defining which property determines the order.

Key Takeaways

• Array sorting arranges elements according to a defined ordering rule.
• Arrays can be sorted in ascending, descending, or custom order.
• Common algorithms include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.
• O(n log n) sorting algorithms are commonly used for larger datasets.
• Stable sorting preserves the relative order of elements with equal keys.
• In-place sorting reduces the need for additional storage, depending on the implementation.
• JavaScript's sort() method accepts a comparison function for custom ordering.
• Numeric arrays should normally use (a, b) => a - b for ascending numeric sorting.
• Sorting can make subsequent operations such as binary search possible or more efficient.