Array Sorting

Overview

Array Sorting is the process of arranging array elements in a specific order (ascending or descending). While most languages provide built-in sort functions, understanding sorting algorithms is crucial for optimization, custom comparators, and solving sorting-related problems.

Common sorting algorithms:

• Quick Sort - O(n log n) average, O(n²) worst case
• Merge Sort - O(n log n) guaranteed
• Heap Sort - O(n log n) guaranteed
• Counting Sort - O(n + k) for small range
• Radix Sort - O(d * n) for integers

Array sorting is particularly useful for:

• Preparing data for algorithms
• Custom ordering
• Finding kth element
• Merging sorted arrays
• Interval problems

Pattern 1: Quick Sort

Divide and conquer sorting algorithm.

function quickSort(nums: number[], left: number = 0, right: number = nums.length - 1): void {
  if (left >= right) return;
  
  const pivotIndex = partition(nums, left, right);
  quickSort(nums, left, pivotIndex - 1);
  quickSort(nums, pivotIndex + 1, right);
}

function partition(nums: number[], left: number, right: number): number {
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

Time: O(n log n) average, O(n²) worst, Space: O(log n)

Pattern 2: Merge Sort

Stable divide and conquer sorting.

function mergeSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums;
  
  const mid = Math.floor(nums.length / 2);
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));
  
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, 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));
}

Time: O(n log n), Space: O(n)

In-place merge sort:

function mergeSortInPlace(nums: number[], left: number = 0, right: number = nums.length - 1): void {
  if (left >= right) return;
  
  const mid = Math.floor((left + right) / 2);
  mergeSortInPlace(nums, left, mid);
  mergeSortInPlace(nums, mid + 1, right);
  mergeInPlace(nums, left, mid, right);
}

function mergeInPlace(nums: number[], left: number, mid: number, right: number): void {
  const temp: number[] = [];
  let i = left, j = mid + 1;
  
  while (i <= mid && j <= right) {
    if (nums[i] <= nums[j]) {
      temp.push(nums[i++]);
    } else {
      temp.push(nums[j++]);
    }
  }
  
  while (i <= mid) temp.push(nums[i++]);
  while (j <= right) temp.push(nums[j++]);
  
  for (let k = 0; k < temp.length; k++) {
    nums[left + k] = temp[k];
  }
}

Pattern 3: Heap Sort

Sort using heap data structure.

function heapSort(nums: number[]): void {
  const n = nums.length;
  
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(nums, n, i);
  }
  
  // Extract elements from heap
  for (let i = n - 1; i > 0; i--) {
    [nums[0], nums[i]] = [nums[i], nums[0]];
    heapify(nums, i, 0);
  }
}

function heapify(nums: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && nums[left] > nums[largest]) {
    largest = left;
  }
  if (right < n && nums[right] > nums[largest]) {
    largest = right;
  }
  
  if (largest !== i) {
    [nums[i], nums[largest]] = [nums[largest], nums[i]];
    heapify(nums, n, largest);
  }
}

Time: O(n log n), Space: O(1)

Pattern 4: Counting Sort

Sort integers in small range.

function countingSort(nums: number[]): number[] {
  const min = Math.min(...nums);
  const max = Math.max(...nums);
  const range = max - min + 1;
  
  const count = new Array(range).fill(0);
  
  // Count frequencies
  for (const num of nums) {
    count[num - min]++;
  }
  
  // Build sorted array
  const result: number[] = [];
  for (let i = 0; i < range; i++) {
    while (count[i] > 0) {
      result.push(i + min);
      count[i]--;
    }
  }
  
  return result;
}

Time: O(n + k), Space: O(k) where k is range

Pattern 5: Custom Comparator Sorting

Sort with custom comparison function.

// Sort by absolute value
function sortByAbsoluteValue(nums: number[]): number[] {
  return [...nums].sort((a, b) => Math.abs(a) - Math.abs(b));
}

// Sort strings by length then alphabetically
function sortStrings(strings: string[]): string[] {
  return [...strings].sort((a, b) => {
    if (a.length !== b.length) {
      return a.length - b.length;
    }
    return a.localeCompare(b);
  });
}

// Sort 2D array by multiple criteria
function sort2DArray(arr: number[][]): number[][] {
  return [...arr].sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return a[1] - b[1];
  });
}

Time: O(n log n), Space: O(n)

Pattern 6: Kth Largest/Smallest Element

Find kth largest element using quick select.

function findKthLargest(nums: number[], k: number): number {
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(nums: number[], left: number, right: number, k: number): number {
  if (left === right) return nums[left];
  
  const pivotIndex = partition(nums, left, right);
  
  if (k === pivotIndex) {
    return nums[k];
  } else if (k < pivotIndex) {
    return quickSelect(nums, left, pivotIndex - 1, k);
  } else {
    return quickSelect(nums, pivotIndex + 1, right, k);
  }
}

function partition(nums: number[], left: number, right: number): number {
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

Time: O(n) average, O(n²) worst, Space: O(1)

Using heap:

function findKthLargestHeap(nums: number[], k: number): number {
  const heap = new MinHeap();
  
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop();
    }
  }
  
  return heap.peek();
}

Time: O(n log k), Space: O(k)

Pattern 7: Sort Colors (Dutch National Flag)

Sort array of 0s, 1s, and 2s in-place.

function sortColors(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(1)

Pattern 8: Merge Sorted Arrays

Merge two sorted arrays.

function mergeSortedArrays(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;
  
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
    } else {
      nums1[k] = nums2[j];
      j--;
    }
    k--;
  }
  
  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}

Time: O(m + n), Space: O(1)

Pattern 9: Sort Array by Parity

Move all even numbers before odd numbers.

function sortArrayByParity(nums: number[]): number[] {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    while (left < right && nums[left] % 2 === 0) left++;
    while (left < right && nums[right] % 2 === 1) right--;
    
    if (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
  
  return nums;
}

Time: O(n), Space: O(1)

Maintain relative order:

function sortArrayByParityStable(nums: number[]): number[] {
  const evens: number[] = [];
  const odds: number[] = [];
  
  for (const num of nums) {
    if (num % 2 === 0) {
      evens.push(num);
    } else {
      odds.push(num);
    }
  }
  
  return [...evens, ...odds];
}

Time: O(n), Space: O(n)

Pattern 10: Largest Number from Array

Form largest number from array of integers.

function largestNumber(nums: number[]): string {
  const sorted = nums.map(String).sort((a, b) => {
    const ab = a + b;
    const ba = b + a;
    return ba.localeCompare(ab);
  });
  
  // Handle leading zeros
  if (sorted[0] === '0') return '0';
  
  return sorted.join('');
}

Time: O(n log n), Space: O(n)

Key insight: Compare concatenated strings: "9" + "34" vs "34" + "9".

Pattern 11: Sort Array by Frequency

Sort array by frequency, then by value.

function sortByFrequency(nums: number[]): number[] {
  const freq = new Map<number, number>();
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  return [...nums].sort((a, b) => {
    const freqA = freq.get(a)!;
    const freqB = freq.get(b)!;
    
    if (freqA !== freqB) {
      return freqA - freqB; // Lower frequency first
    }
    return b - a; // Higher value first if same frequency
  });
}

Time: O(n log n), Space: O(n)

Pattern 12: Wiggle Sort

Rearrange array so nums[0] < nums[1] > nums[2] < nums[3]...

function wiggleSort(nums: number[]): void {
  for (let i = 1; i < nums.length; i++) {
    if ((i % 2 === 1 && nums[i] < nums[i - 1]) ||
        (i % 2 === 0 && nums[i] > nums[i - 1])) {
      [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
    }
  }
}

Time: O(n), Space: O(1)

Wiggle Sort II (strict alternation):

function wiggleSortII(nums: number[]): void {
  const sorted = [...nums].sort((a, b) => a - b);
  const n = nums.length;
  const mid = Math.floor((n + 1) / 2);
  
  // Interleave smaller and larger halves
  for (let i = 0; i < n; i++) {
    if (i % 2 === 0) {
      nums[i] = sorted[mid - 1 - Math.floor(i / 2)];
    } else {
      nums[i] = sorted[n - 1 - Math.floor(i / 2)];
    }
  }
}

Time: O(n log n), Space: O(n)

When to Use Different Sorting Algorithms

Quick Sort:

• General purpose, average case O(n log n)
• In-place, cache-friendly
• Use when: Average performance matters, space is limited

Merge Sort:

• Guaranteed O(n log n)
• Stable sort
• Use when: Need stability, worst-case guarantee

Heap Sort:

• Guaranteed O(n log n)
• In-place
• Use when: Need guaranteed performance, limited space

Counting Sort:

• O(n + k) for small range
• Use when: Range is small (e.g., 0-100)

Built-in Sort:

• Usually optimized (Timsort)
• Use when: No special requirements

Template (Quick Sort)

function quickSortTemplate(nums: number[], left: number, right: number): void {
  if (left >= right) return;
  
  const pivotIndex = partition(nums, left, right);
  quickSortTemplate(nums, left, pivotIndex - 1);
  quickSortTemplate(nums, pivotIndex + 1, right);
}

function partition(nums: number[], left: number, right: number): number {
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

Template (Custom Comparator)

function customSort(nums: number[], compareFn: (a: number, b: number) => number): number[] {
  return [...nums].sort(compareFn);
}

// Example: Sort by absolute value
const sorted = customSort(nums, (a, b) => Math.abs(a) - Math.abs(b));

Time and Space Complexity Summary

• Quick Sort: O(n log n) avg, O(n²) worst time, O(log n) space
• Merge Sort: O(n log n) time, O(n) space
• Heap Sort: O(n log n) time, O(1) space
• Counting Sort: O(n + k) time, O(k) space
• Built-in Sort: O(n log n) time, O(n) space

Practice Tips

1. Choose algorithm - Based on constraints and requirements
2. Custom comparator - For complex sorting criteria
3. Stability - Use merge sort if order matters
4. In-place - Quick sort or heap sort for space constraints
5. Small range - Counting sort for integers in small range

Common Mistakes

1. Modifying original - Not copying array before sorting
2. Comparator logic - Wrong comparison order
3. Index errors - Off-by-one in partition/merge
4. Stability - Not considering if stability matters
5. Edge cases - Empty array, single element, duplicates

Related Concepts

• Quick Select - For finding kth element
• Heap - For priority queue and heap sort
• Two Pointers - Used in partition operations
• Divide and Conquer - Core of merge/quick sort

Array sorting is fundamental to many algorithms. Master these patterns, and you'll efficiently solve sorting-related problems and optimize your solutions in coding interviews.