Sorting algorithm classification

According to sorting ideas, it can be divided into: Insertion sort, exchange sort, selection sort, merge sort, and radix sort.

Time complexity: The average time complexity of common comparison sorting is O(n²) and O(n log₂ n), etc.Specific analysis requires distinguishing between best, average and worst cases; Hill sorting also depends on the incremental sequence, and radix sorting depends on the number of records, digits and cardinality.

Stability: If after sorting, records with equal keywords still maintain their original relative order, the sorting algorithm is said to be stable.

For example, when sorting by numerical keywords, the stable sorting result of [2A, 1, 2B] is [1, 2A, 2B], and the two records with the keyword 2 are still arranged according to A and B.Letters are used only to identify records and are not included in comparisons; these tags are conceptual examples, not JavaScript values.

The following code sorts the values in ascending order. Unless otherwise specified, it will directly modify the incoming array.

Each code block can run independently.The comparison sort example assumes that the input is a dense array (no gaps), and each element is a finite Number, excluding NaN; the example does not repeatedly check these preconditions.The input range and verification of radix sort are explained in the corresponding chapters.

insertion sort

Basic idea:

In each step, a record to be sorted is inserted into the appropriate position of the previously sorted interval according to its key size until all records are sorted.

concretely realized 3️⃣ Different algorithms:

• Direct insertion sort: Find the insertion position sequentially, simple to implement.
• Half-fold insertion sort: find the insertion position by half.
• Hill sort: Insertion sort by increments of successive reductions.

1️⃣ direct insertion sort

Sort process: Perform n-1 insertions into a non-empty array: treat the first record as an ordered interval, and insert one by one starting from the second record until the entire array is sorted.

function insertionSort(L) {
  for (let i = 1; i < L.length; i++) {
    if (L[i] < L[i - 1]) {
      const temp = L[i];
      let j = i - 1;
      while (j >= 0 && temp < L[j]) {
        L[j + 1] = L[j];
        --j;
      }
      L[j + 1] = temp;
    }
  }
  return L;
}
console.log(insertionSort([2,6,3,1,4])); // [1,2,3,4,6]

Algorithm Analysis:

Time complexity: The best is O(n) when ordered, and the average and worst is O(n²).
Extra space complexity: O(1).
Stability: Stable, only elements whose keywords are strictly greater than the record to be inserted are moved, and the relative order of equal records is not changed.

2️⃣ half insertion sort

Sort process: When inserting L[i], use half search to find the insertion position in the previous ordered interval, and then move the element backward to make room.To maintain stability, the search continues to the right when equal, and the new record is placed after the existing equal record.

function binaryInsertionSort(L) {
  for (let i = 1; i < L.length; ++i) {
    const temp = L[i];
    let low = 0;
    let high = i - 1;
    while (low <= high) {
      const m = low + Math.floor((high - low) / 2);
      if (temp < L[m]) {
        high = m - 1;
      } else {
        low = m + 1;
      }
    }
    // 查找结束时 low = high + 1，即插入位置
    for (let j = i; j > low; --j) {
      L[j] = L[j - 1];
    }
    L[low] = temp;
  }
  return L;
}
console.log(binaryInsertionSort([8,2,3,1,5,6,4]));

Algorithm Analysis:

Reduces the number of comparisons required to locate the insertion position, but does not reduce the number of element moves.Actual performance depends on whether the input is ordered, and the cost of comparing and moving.

Time complexity: This implementation will perform a binary search one after another even if the input is sorted. The best is O(n log₂ n); the average and worst are still O(n²).
Extra space complexity: O(1).
Stability: Stable, search to the right when equal, and retain the original order of equal records.

3️⃣Hill sort

Basic idea:

The records separated by increment dk are formed into a subsequence, and direct insertion sorting is performed respectively; the grouping here is not continuous segmentation.Reduce the increment step by step, and finally perform direct insertion sort on all records with an increment of 1.

Sort process: The following figure and code use 3, 2, 1 by default.The first few passes reduce reverse order by moving across locations, and the last pass completes global sorting.The moves required by direct insertion sort can usually be reduced when using an appropriate sequence of increments. Actual performance depends on the increments and input.

The initial sequence in the figure is 21, 25, 49, 25*, 16, 08. The asterisk is used to distinguish two records with the same keyword 25.After sorting, 25* appears before ordinary 25, indicating that Hill sorting is unstable.

The increment parameter gaps must be a non-empty array, each increment is a positive safe integer, strictly decreasing, and the last one is 1.The function first verifies the entire incremental sequence before modifying the input array to avoid incorrect parameters causing partial sorting or returning unsorted results.

function shellSort(L, gaps = [3, 2, 1]) {
  const message = "增量序列必须为正安全整数、严格递减并以 1 结尾";
  if (!Array.isArray(gaps) || gaps.length === 0 || gaps[gaps.length - 1] !== 1) {
    throw new RangeError(message);
  }
  let previous = Infinity;
  for (const gap of gaps) {
    if (!Number.isSafeInteger(gap) || gap <= 0 || gap >= previous) {
      throw new RangeError(message);
    }
    previous = gap;
  }
  for (const gap of gaps) {
    shellInsert(L, gap); // 按当前增量进行一趟插入排序
  }
  return L;
}

function shellInsert(L, dk) {
  for (let i = dk; i < L.length; ++i) {
    if (L[i] < L[i - dk]) {
      const temp = L[i];
      let j = i - dk;
      while (j >= 0 && temp < L[j]) {
        L[j + dk] = L[j];
        j -= dk;
      }
      L[j + dk] = temp;
    }
  }
}
console.log(shellSort([21,25,49,25,16,8], [3,2,1])); // [8,16,21,25,25,49]

Algorithm Analysis:

Time complexity: Depends on the number of records n and the incremental sequence, and cannot be uniformly written as a certain empirical power.When this article uses 3, 2, and 1 fixedly, the best ordered input is O(n), and the average (random permutation) and worst case are both O(n²): the first pass performs direct insertion sorting on 3 subsequences with a length of about n/3, and the average and worst workloads are already quadratic.When m increments are customized, verification also requires O(m) time.
Extra space complexity: O(1).
Stability: Unstable, moving across locations may change the relative order of equal records.

The default increment is used to match the graphic demonstration; for longer arrays, the increment sequence should be selected based on theoretical analysis and actual performance.Hill sorting relies on subscript access to incremented elements and is not suitable for direct use in linked lists.

swap sort

Basic idea:

Compare them pairwise, and exchange them if a reverse order occurs, until all records are sorted.

1️⃣bubble sort

Sort process: Compare adjacent records from left to right, and exchange them if they are in reverse order, so that the maximum value of the current unsorted interval is moved to the end.Each pass reduces one position; when there is no exchange in a certain pass, it means that the array is in order and can end early.

function bubbleSort(L) {
  let m = L.length - 1;
  let flag = true;
  while (m > 0 && flag) {
    flag = false;
    for (let j = 0; j < m; j++) {
      if (L[j] > L[j + 1]) { // 从小到大排
        flag = true;
        [L[j], L[j + 1]] = [L[j + 1], L[j]]; // 交换数据
      }
    }
    m--;
  }
  return L;
}
console.log(bubbleSort([21,25,49,25,16,18,9,88,7,3,6,30]));

Algorithm Analysis:

Assuming the number of records is n, the number of comparisons and the number of moves are related to the initial arrangement.

Best case: When ordered, only one check is required, n-1 comparisons are made without swapping, and the time is O(n).
Worst case: Reverse order requires n(n-1)/2 comparisons and exchanges, and the time is O(n²).
Average time complexity: O(n²).
Extra space complexity: O(1).
Stability: Stable, equal records will not be interchanged.

2️⃣quick sort

Basic idea:

Select an element (such as the first one) as the pivot value.

Through one division, the benchmark is placed in the final position, the left element is not larger than the benchmark, and the right element is not smaller than the benchmark.Then recursively sort the left and right subsequences until there is only one element left in the subsequence or it is empty.

Features of the quick sort implementation in this article:

1. The first element is used as the benchmark, and the two subscripts are scanned alternately from both ends to the middle and records are exchanged to complete a division.This is the division method used in this article, other implementations can also use different methods.
2. Recursively sorts the subsequences on both sides of the basis, ending when the subsequence is empty or has only one element.

// 快排
function quickSort(L, low = 0, high = L.length - 1) {
  if (low < high) {
    const pivotloc = partition(L, low, high);
    quickSort(L, low, pivotloc - 1);
    quickSort(L, pivotloc + 1, high);
  }
  return L;
}
// 快速排序的一次划分
function partition(L, low, high) {
  const pivotkey = L[low];
  while (low < high) {
    while (low < high && L[high] >= pivotkey) {
      --high;
    }
    [L[low], L[high]] = [L[high], L[low]]; // 交换两个位置
    while (low < high && L[low] <= pivotkey) {
      ++low;
    }
    [L[low], L[high]] = [L[high], L[low]]; // 交换位置
  }
  return low;
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(quickSort(L));

Algorithm Analysis:

Time complexity: When each division is balanced, it is best to be O(n log₂ n); under the assumption that the keywords are different and the input is randomly arranged, the average is also O(n log₂ n).Actual performance is affected by benchmark selection, input order, and number of repeated keywords.

At worst, each benchmark is the minimum or maximum value of the current subsequence, excluding only one element.The workload of each division is approximately n-1, n-2,...,1, and the total time is O(n²).This article chooses the first element as the benchmark. Ordered, reversed, or all equal inputs will cause this kind of degradation.

Extra space complexity: The partitioning process is O(1), and the recursion stack space depends on the recursion tree height; under the above random arrangement assumption, the average is O(log₂ n), and the worst is O(n).
Stability: Unstable, swapping across locations may change the relative order of equal records.

This example is used to demonstrate the recursive implementation of the first element basis.Larger degenerate input may also cause JavaScript call stack overflow; in practical applications, it can be improved by combining random benchmarks, three-way division for repeated keywords, and only recursing the shorter side and looping to process the longer side.

selection sort

Basic idea:

Each pass selects the record with the smallest or largest key from the unsorted interval, adding one element to the ordered interval.Simple selection sort directly finds the minimum value, while heap sort uses the heap structure to obtain the maximum value.

1️⃣Simple selection sort

Sort process: After finding the smallest record in each pass, it is exchanged with the first record of the unsorted interval.

function selectionSort(L) {
  for (let i = 0; i < L.length - 1; i++) {
    let k = i;
    for (let j = i + 1; j < L.length; j++) {
      if (L[j] < L[k]) {
        k = j;
      }
    }
    if (k !== i) {
      [L[i], L[k]] = [L[k], L[i]];
    }
  }
  return L;
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(selectionSort(L));

Algorithm Analysis:

Each trip can be exchanged at most once, and the total number of exchanges is at most n-1.If the number of moves is calculated according to the traditional counting method in which one exchange is equivalent to three record assignments:

Minimum moves: 0.
Maximum number of moves: 3(n-1).
Time complexity: Best, average and worst are all O(n²), and the number of comparisons is n(n-1)/2.
Extra space complexity: O(1).
Stability: Unstable.For example, [2A, 2B, 1C] becomes [1C, 2B, 2A] after the first exchange, and the order of the two records with the key 2 changes.

2️⃣Heap sort

A heap can be represented as a complete binary tree using an array.The large top heap requires that the value of each parent node is not less than its child node, while the small top heap requires that the value of the parent node is not greater than its child node; the heap does not require a size relationship between the left and right subtrees.

The root node of the big top heap is the maximum value.Swap it with the last element in the valid heap range, put the maximum value into the sorted area at the end of the array, reduce the heap range, and restore the big top heap.Repeat this process to get an ascending array.

How to restore the big top heap after moving the top of the heap to the end?

1. Swapping the top and bottom elements of the heap, excluding the sorted elements at the end, the new root node may need to sink.
2. Compare the two children of the current node and select the larger one; if the child is larger, swap and move to the child's position to continue checking.
3. When the current node is not smaller than the child, or there are no children, the adjustment ends.

The above figure demonstrates the initial heap construction: starting from the last non-leaf node 42, adjusting from the bottom up.When the root node is finally adjusted, 46 is first exchanged with 94, and then exchanged with 70 along the left subtree.After the exchange, you need to continue checking downwards to restore the heap properties of the entire subtree.

// 大顶堆
function adjustHeap(L, i, length) {
  let k = i * 2 + 1; // 当前结点的左孩子
  while (k < length) {
    if (k + 1 < length && L[k] < L[k + 1]) {
      ++k; // 选择较大的孩子
    }
    if (L[i] >= L[k]) {
      break;
    }
    [L[i], L[k]] = [L[k], L[i]];
    i = k; // 沿交换后的孩子位置继续下沉
    k = i * 2 + 1;
  }
}

function heapSort(arr) {
  // 从最后一个非叶子结点开始，自底向上构建大顶堆
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; --i) {
    adjustHeap(arr, i, arr.length);
  }
  // 交换堆顶与末尾元素，缩小有效堆的范围并重新调整
  for (let j = arr.length - 1; j > 0; --j) {
    [arr[0], arr[j]] = [arr[j], arr[0]];
    adjustHeap(arr, 0, j);
  }
  return arr;
}

const arr = [46,55,13,42,94,5,17,70];
console.log(heapSort(arr));

Algorithm Analysis:

Time complexity: It takes O(n) time to build a heap from the bottom up; after each removal of the top of the heap, adjustment requires at most O(log₂ n) time, and the overall worst-case scenario is O(n log₂ n).This implementation ends immediately when all are equal, preferably O(n); on average O(n log₂ n).
Extra space complexity: O(1).
Stability: Unstable, the exchange of elements at the top and the end of the heap may change the relative order of equal records.

Merge sort (two-way merge)

Basic idea: Merge two ordered subsequences into a new ordered sequence.

Sort process: The code in this article uses top-down recursion: first split the array into left and right halves, sort them respectively, and then merge the two ordered arrays.When the array is empty or has only one element, a copy is returned directly.

It can also be done from the bottom up: treat the initial array as n ordered subsequences of length 1, merge them two by two, get ⌈n/2⌉ subsequences of length 2 or 1 in the first pass, and then merge them one by one until the entire array is in order; ⌈n/2⌉ means rounding up.

The following implementation merges ordered arrays through two subscripts without repeatedly deleting the first item of the array, and returns a new array while retaining the original array.

// 归并排序
function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}
function mergeSort(items) {
  if (items.length <= 1) {
    return items.slice();
  }
  const middle = Math.floor(items.length / 2);
  const left = items.slice(0, middle);
  const right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(mergeSort(L));

Algorithm Analysis:

Time complexity: The best, average and worst implementations of this article are all O(n log₂ n).
Extra space complexity: O(n) for merging arrays; the recursive stack requires another O(log₂ n), and the total extra space is still O(n).
Stability: Stable, when merging equal keywords, the record on the left will be taken first.

Radix sort

The previous sorting method mainly determines the order by comparing keywords.Radix sorting performs "distribution" and "collection" according to each keyword, and does not directly compare the size of complete keywords.

According to the processing order of keywords, it can be divided into:

1. Most Significant Digit first (MSD).
2. Least Significant Digit first (LSD).

By storage structure: Array bucket or linked list can be used.Chained radix sorting is an implementation using linked lists. This section will explain it in LSD order.

The array bucket implementation of decimal LSD radix sorting is given below. Only supports dense arrays composed of non-negative safe integers (each value is between 0 and Number.MAX_SAFE_INTEGER), returns a new array, and retains the original array.The array length is taken directly from data.length, and the number of buckets is determined by base 10.

Use for...of to check each element. The gaps will be read as undefined and rejected; methods such as some() that skip the gaps cannot complete this verification.

// 求数组中数值的最大十进制位数，0 按一位处理
function maxDigits(data) {
  let digits = 1;
  let threshold = 10;
  for (const value of data) {
    while (value >= threshold) {
      threshold *= 10;
      ++digits;
    }
  }
  return digits;
}

function radixSort(data) {
  if (!Array.isArray(data)) {
    throw new TypeError("基数排序的输入必须是数组");
  }
  for (const value of data) {
    if (!Number.isSafeInteger(value) || value < 0) {
      throw new RangeError("基数排序仅支持由非负安全整数组成的稠密数组");
    }
  }
  let result = data.slice();
  if (result.length <= 1) return result;

  const digits = maxDigits(result);
  const base = 10;
  let place = 1; // 依次处理个位、十位、百位……
  for (let i = 0; i < digits; ++i) {
    const buckets = Array.from({ length: base }, () => []);
    for (const value of result) {
      const digit = Math.floor(value / place) % base;
      buckets[digit].push(value); // 保持相同位值记录的原有顺序
    }

    const next = [];
    for (const bucket of buckets) {
      for (const value of bucket) next.push(value);
    }
    result = next;
    place *= base;
  }
  return result;
}

const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(radixSort(L)); // [3,6,7,9,16,18,21,25,25,30,49,88]

Algorithm analysis: Suppose the number of records is n, the maximum number of digits is d, and the base is r.

Time complexity: Each pass allocates n records and collects r buckets, a total of d passes, which is O(d(n + r)); input verification requires O(n) time, which does not change the overall complexity.
Extra space complexity: O(n + r).
Stability: Stable, buckets are added and collected in the original order, and the relative order of records with the same place value is retained in each pass.

1️⃣Most significant first (MSD)

First group by the highest keyword k₁, then continue to group by the next highest keyword k₂ within each group, process to the lowest keyword in sequence, and finally connect in the order of the groups.

Decimal numbers can be regarded as multi-keyword records. If there are insufficient digits, 0 will be added in front.The following 063 and 008 are only used for zero padding display, and the JavaScript values ​​​​should be written as 63 and 8.

The following is sorted in MSD order:

Sort by highest

{063，064，008，083}，{109，184}，{278，269}，{589，505}，

Sort by highest order within each group

{008},{063,064},{083},{109},{184},{269},{278},{505},{589},

Sort by lowest digit

{008},{063},{064},{083},{109},{184},{269},{278},{505},{589},

Finally, all the subsequences are linked together in order to obtain the arranged sequence.

2️⃣Least significant first (LSD)

Sort by the lowest bit first, then sort by the lowest bit, until the highest bit is processed.Each pass sorts the entire sequence.

Key conditions: Each sorting pass must be stable in order to retain the results of the previous low-order sorting.The code in this section ensures stability through sequential appending and sequential collection within the bucket.

lowest priority method

278，109，063，930，184，589，269，008，083

Sort by ones

930，063，083，184，278，008，109，589，269

Sort by tens

008，109，930，063，269，278，083，184，589

Sort by hundreds

008，063，083，109，184，269，278，589，930

chained radix sort

Prerequisites:

• Know the primary and secondary relationship of keywords at all levels
• Know the value range of keywords at all levels

Sort keywords using Distribute and Collect:

The lowest bit is processed first, and each record is "distributed" to the corresponding chain queue according to the value of this bit keyword. Records in the same queue are added to the queue in the original order.

Connect each queue in order from small to large bit values, complete the "collection", and then continue to process the next bit.Use the first-in-first-out order of the queue to ensure stable allocation and collection for each trip.

Algorithm analysis: Same as the aforementioned array bucket implementation, the time complexity is O(d(n + r)), the extra space is O(n + r), and the stability is guaranteed by the sequential enqueuing and collection of the queue.When represented by a static linked list, n record link positions and r head and tail pointers of the queue can be used, for a total of n + 2r additional link positions.

Sorting algorithm comparison

The following is a comparison of the implementation of this article.Extra space contains the recursion stack; in radix sorting, d is the maximum number of digits and r is the radix.

Sorting method	Best time	Average time	Worst time	Extra space	Stability	Modify original array
Direct insertion sort	O(n)	O(n²)	O(n²)	O(1)	Stable	Yes
Half-fold insertion sort	O(n log₂ n)	O(n²)	O(n²)	O(1)	Stable	Yes
Hill sort (increment 3, 2, 1)	O(n)	O(n²)	O(n²)	O(1)	Unstable	Yes
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	Stable	Yes
Quicksort	O(n log₂ n)	O(n log₂ n)	O(n²)	Average O(log₂ n), worst O(n)	Unstable	Yes
Simple selection sort	O(n²)	O(n²)	O(n²)	O(1)	Unstable	Yes
Heap sort	O(n) (when all equal)	O(n log₂ n)	O(n log₂ n)	O(1)	Unstable	Yes
Merge sort	O(n log₂ n)	O(n log₂ n)	O(n log₂ n)	O(n)	Stable	No
LSD radix sort	O(d(n + r))	O(d(n + r))	O(d(n + r))	O(n + r)	Stable	No

One row of Hill sorting corresponds to the default fixed increment of this article, and the average time is analyzed in random order; reanalysis is required when changing the increment sequence.The average complexity of quick sort adopts the previous assumptions of mutually different keywords and random arrangement.The O(n) best time of heap sort corresponds to the implementation of early ending sinking when all are equal in this article.

In-place modification methods return the passed array; merge sort and radix sort always return new arrays, including empty arrays and single-element arrays.

You can combine these features when choosing:

• When the array is small or nearly ordered, you can consider direct insertion sorting; if the comparison cost is high, half insertion can reduce the number of comparisons to find the insertion position, but elements still need to be moved.
• When you need a worst-case O(n log₂ n) comparison sort, you can consider heap sort or merge sort; merge sort also maintains stability and requires O(n) additional space.
• For non-negative safe integers and limited number of bits, one can consider this article's LSD radix sort while evaluating the additional space required by the buckets.The performance of Hill sort and quick sort needs to be judged by combining incremental or benchmark strategies and input distribution.