Sort

Insertion Sort
Merge Sort
Bubble Sort
Selection Sort
Counting Sort
Quick Sort
Median Of Two Sorted Arrays

Insertion Sort

Description

Sort an array of numbers using insertion sort. Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list.

Solution

Start with the second element a[2], and assume the first element a[1] is sorted(With only one element in an array, it's always sorted). Compare the a[2] and a[1].

If a[2] is bigger, no action is needed; if smaller, move a[2] ahead of a[1].

After first iteration, the first two elements are sorted.

Now look at the third element a[3], and compare it with the previous one (the largest element in the sorted sub-array). If the a[3] is bigger, no action is need; if smaller, move it forward by one position until its value is bigger than the previous one or gets to the head of the array.

After the second iteration, the first three elements are sorted.

Now look at the fourth element a[4] and use the previous method to put a[4] to the right position so that a[1] to a[4] are sorted.

Iterate through the process until the last element is put to the right position then the array is sorted.

Example

a = [23, 1, 10, 5, 2]

The first iteration starts with a[1], which is number 1 and compare it with its previous number, which is 23, because 1 is smaller, move it forward.

After the first iteration, the array is: [1, 23, 10, 5, 2], where the first two elements [1, 2] are sorted.

In the second iteration, look at a[2], which is number 10. Compare a[2] with its previous element recursively, until it's bigger than its previous one. Basically, put the number in the right place of the previous sorted sub-array.

After the second iteration, the array is: [1, 10, 23, 5, 2], where the first three elements [1, 10, 23] are sorted.

In the third iteration, look at a[3], which is number 5, compare and move it forward until it's bigger than its previous number.

After the third iteration, the array is [1, 5, 10, 23, 2], where the first four elements [1, 5, 10, 23] are sorted;

In the fourth iteration, look at a[4], which is number 2, compare and move it forwad until it's bigger than its previous number.

After the fourth iteration, the array is [1, 2, 5, 10, 23] and the array is fully sorted.

Performance

Best-case: O(n)

Worse-case: O(n²)

Average: O(n²)

Notes

It's a in-place sorting algorithm.
Simple and straightforward implementation.
Not efficient for large dataset.

Implementation

Back to index

Merge Sort

Description

Sort an array of numbers using merge sort. Merge sort follows the divide-and-conquer approach. That is to say, divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.

Solution

Divide the array recursively into two halves until no more can be divided.
Each sub-array is sorted individually using merge sort.
The sorted sub-arrays are merged back together in sorted order. The process continues until all elements from both sub-arrays have been merged.

Example

a = [38, 27, 43, 10]

Divide array from the middle and it becomes: [38, 27], [43, 10]

[38, 27] is further divided into [38] and [27];

[43, 10] is further divided into [43] and [10].

Then [38], [27], [43], [10] are already sorted respectively.

Now, merge [38] and [27] -> [27, 38];

merge [43, 10] -> [10, 43].

Merge [27, 38] and [10, 43] to get the final sorted array [10, 27, 38, 43]

Performance

Best-case: O(n log n)

Worse-case: O(n log n)

Average: O(n log n)

Auxiliary space: O(n)

It's a bit tricky to understand why merge sort has this time complexity. It's because it uses divide and conquer approach by dividing an array into halves recursively until each sub-array has one element. Think this approach will generate a recursion tree like this:

                   [n elements]
                  /            \
        [n/2 elements]        [n/2 elements]
        /         \             /         \
   [n/4 el]     [n/4 el]    [n/4 el]   [n/4 el]
   ...
     [2]         [2]         [2]        [2]
    /   \       /   \       /   \      /   \
   [1]  [1]   [1]   [1]   [1]   [1]  [1]   [1]

The tree has log₂n levels, which means the array is divided log₂n times. This is dividing process.

Why log₂n levels? It's because n is divided by 2 recursively until it becomes 1. This process can be translated to this formula: n / 2^k = 1. To solve this formula: k = log₂n

This tree has n leaves, which means it takes O(n) work to merge. Therefore, the overall complexity is O(n log n)

Notes

Not in place sorting. It does not change the original order of the array. Rather, it returns an sorted array.
Efficient in terms of time complexity.
Simple and straightforward as long as you understand recursion algorithm.
Requires additional space to store sub-arrays.

Implementation

Back to index

Bubble Sort

Description

Sort an array using bubble sort. Bubble sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Solution

Repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes through the list are repeated until no swaps have to be performed during a pass, meaning that the list has become fully sorted.

Example

a=[3, 1, 6, 5, 2, 4]

I. First step:

Compare a[0] and a[1]: 3 > 1, swap: [1, 3, 6, 5, 2, 4]
Compare a[1] and a[2]: 3 < 6, no swap: [1, 3, 6, 5, 2, 4]
Compare a[2] and a[3]: 6 > 5, swap: [1, 3, 5, 6, 2, 4]
Compare a[3] and a[4]: 6 > 2, swap: [1, 3, 5, 2, 6, 4]
Compare a[4] and a[5]: 6 > 4, swap: [1, 3, 5, 2, 4, 6]

After first step, biggest number 6 is "bubbled" to the end of array.

II. Second step

Compare a[0] and a[1]: 1 < 3, no swap: [1, 3, 5, 2, 4, 6]
Compare a[1] and a[2]: 3 < 5, no swap: [1, 3, 5, 2, 4, 6]
Compare a[2] and a[3]: 5 > 2, swap: [1, 3, 2, 5, 4, 6]
Compare a[3] and a[4]: 5 > 4, swap: [1, 3, 2, 4, 5, 6]

After second step, 5 is sorted to the right place.

Repeat the above steps, until the whole array is iterated and sorted.

Performance

Best-case: O(n)

Worse-case: O(n²)

Average: O(n²)

Notes

In place sorting.
The least efficient sorting algorithm. Rarely used in practice except for educational purposes.
Comparison with insertion sort. They have the same time complexity, but in practice, insertion sort is considered more efficient than bubble sort because insertion sort is more adaptive, meaning it becomes more efficient if the given array is partially sorted. If the array is partially sorted, comparison and swap can stop earlier for insertion sort, while bubble sort still need to iterate through the whole array.

Implementation

Back to index

Selection Sort

Description

Sort an array using selection sort.

Solution

Divide the given array into two parts: the left part of sub-array, which is sorted and the remaining right part unsorted items.

The left part sorted sub-array started from empty and the unsorted sub-array is literally the whole array.

Iterate through the remaining numbers to find out the smallest number and put it to the tail of the sorted sub-array(swap it with the leftmost number in the unsorted sub-array). Repeatedly do the same thing to the remaining numbers until all numbers are sorted.

Example

a=[12, 25, 64, 11, 22]

Find out the smallest number in the array, which is 11. Swap 11 with a[0], 12 to move it to the head of the array: [11, 12, 25, 54, 22]
After step 1, the sub-array of [11] is sorted. Find out the smallest number from the remaining numbers, which is a[1] - 12. It's already at the head of the right sub-array: [11, 12, 25, 54, 22].
After step 2, the sub-array of [11, 12] is sorted. Find out the smallest number from the remaining numbers, which is a[4] - 22. Swap it with a[2] - 25 to move it to the head of right sub-array: [11, 12, 22, 54, 25].
Repeat the above steps until the whole array is sorted: [11, 12, 22, 25, 54]

Performance

Best-case: O(n²)

Worse-case: O(n²)

Average: O(n²)

Notes

In place sorting.
Straightforward and easy to understand.
Not efficient sorting algorithm.
Not adaptive.
Not stable, meaning the relative order of the same number might be changed.
Among the three O(n²) sorting algorithms: selection sort, insertion sort and bubble sort, they can be ordered in general: insertion sort > selection sort > bubble sort.

Implementation

Back to index

Counting Sort

Description

Sort an array using counting sort.

Solution

Find out the maximum number of the array - max.
Initialize a counting array with the length of max + 1 and filled the array with 0.
In the first for loop, counting the number of times each element occurs within the given array.
In the second for loop, perform a prefix sum in counting array.
In the third loop, iterate over the given array again and move each element into its sorted position in the sorted array.

Example

a=[4, 2, 2, 8, 3, 3, 1]

Find out the maximum number, say max from the given array.

max = 8
Create an empty array of length(max + 1 = 9) and populate it with all 0s. This array is for storing the count of the elements in the array.

Now, we get the count array: [0, 0, 0, 0, 0, 0, 0, 0, 0](9 0s)
Iterate through the given array, and record the count of each number at their respective index in count array.

For example, number 3 appears 2 times, then the index of 3 in count array should be 2.

After the counting, the count array should be: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Iterate through the count array, and sum the current element with its previous element. (Do cumulative sum of each element)

After accumulation, the count array should be: [0, 1, 3, 5, 6, 6, 6, 6, 7]
Iterate through the given array and place each element in the correct place:

Look at what we get now:

The array to sort: [4, 2, 2, 8, 3, 3, 1]

Counting array: [0, 1, 3, 5, 6, 6, 6, 6, 7]

The sorted array: [?, ?, ?, ?, ?, ?, ?]

Now for element 4 in original array, we get the element at the index = 4 in sorting array, which is 6.

So it means the 6th position(index = 5) of the sorted array should be 4. Now we know where to put the first element in sorted array: [?, ?, ?, ?, ?, 4, ?].

After placing each element, decrease its count by 1. Now the counting array after the first iteration is [0, 1, 3, 5, 5, 6, 6, 6, 7].

As per the above rule, we can work out the sorted array and counting array after each iteration.

After the first element - 4: sorted array: [?, ?, ?, ?, ?, 4, ?], count array: [0, 1, 3, 5, 5, 6, 6, 6, 7]

Now we move to the next element which is 2. As per the above rule, it's not difficult to figure out where to put 2 in sorted array.

After he second element - 2:

sorted array: [?, ?, 2, ?, ?, 4, ?], count array: [0, 1, 2, 5, 5, 6, 6, 6, 7]

After the third element - 2:

sorted array: [?, 2, 2, ?, ?, 4, ?], count array: [0, 1, 1, 5, 5, 6, 6, 6, 7]

After the 4th element - 8:

sorted array: [?, 2, 2, ?, ?, 4, 8], count array: [0, 1, 1, 5, 5, 6, 6, 6, 6]

After the 5th element - 3:

sorted array: [?, 2, 2, ?, 3, 4, 8], count array: [0, 1, 1, 4, 5, 6, 6, 6, 6]

After the 6th element - 3:

sorted array: [?, 2, 2, 3, 3, 4, 8], count array: [0, 1, 1, 3, 6, 6, 6, 6, 7]

After the 7th element - 1:

sorted array: [1, 2, 2, 3, 3, 4, 8], count array: [0, 1, 1, 4, 6, 6, 6, 6, 7]

Performance

Time complexity: O(n+k)

Space complexity: O(n+k)

n is the length of array, k is the maximum number of the array.

Notes

Specifically used for sorting small positive integers.
Stable sorting algorithm.

Implementation

Back to index

Quick Sort

Description

Sort an array using quick sort.

Solution

Based on the idea of divide-and-conquer

Choose a pivot. Select an element from the array as the pivot. The pivot can be the first element, last element, random element or median.
Rearrange the array around the pivot. All elements smaller than the pivot are put on its left; all elements bigger than the pivot are put on its right.
Recursively apply the same process to the two partitioned sub-arrays until there is only one element left in the sub-array.

Example

a = [4, 3, 1, 2, 5, 9, 7, 10, 6]

Select the first element 4 as pivot and divide the array into two sub-arrays, where the numbers less than 4 are on left sub-array and the numbers greater than 4 are on right sub-array.

[3, 1, 2], 4, [5, 9, 7, 10, 6]

Choose 3 as pivot for left sub-array and 5 as pivot for right sub-array and repeat the same process as above.

[1, 2], 3, [], 4, [], 5, [9, 7, 10, 6].

Choose the first element as pivot for each sub-array and repeat.

[], 1, [2], 3, [], 4, [], 5, [7, 6], 9, [10]

The final round:

[], 1, [2], 3, [], 4, [], 5, [6], 7, [], 9, [10]

Now combine the above subarrays and pivots and we get the sorted array: [1, 2, 3, 4, 5, 6, 7, 9, 10]

Performance

Best-case: O(n log n)

Worse-case: O(n²)

Average: O(n log n)

Auxiliary space: O(n)

Notes

Use divide-and-conquer to make it efficient on large data sets.
Fastest algorithm.
Not stable.
Its worst-case time complexity is O(n²). It happens when the pivot is not properly selected.

Implementation

Back to index

Median Of Two Sorted Arrays

Description

Leetcode-4

[Hard] Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Example

nums1 = [1, 2, 5, 8], nums2 = [3, 4, 6, 7, 9] => 5

Explanation: Combine the two sorted arrays nums1 and nums2: [1, 2, 3, 4, 5, 6, 7, 8, 9], so the median is 5.

Solution

There are two solutions to this problem. Both avoid fully merging the two arrays (which would be O(m+n)) by using binary search, giving a better time complexity.

Solution 1: Binary search on partition

The idea is to find a "partition" point in each array such that all elements to the left of the two partitions form the left half of the combined sorted array, and all elements to the right form the right half.

Always binary search on the smaller array (call it nums1 with length m, and the other nums2 with length n). This bounds the binary search to O(log(min(m,n))) and guarantees a valid partition of nums2 always exists.
For a candidate partition index i in nums1 (0 <= i <= m), the matching partition index in nums2 is j = floor((m+n+1)/2) - i, chosen so the left half always has floor((m+n+1)/2) elements (this correctly accounts for both odd and even total length).
Define maxLeft1 = nums1[i-1], minRight1 = nums1[i], maxLeft2 = nums2[j-1], minRight2 = nums2[j] (using -Infinity/Infinity when the index falls outside the array).
A valid partition is found when maxLeft1 <= minRight2 and maxLeft2 <= minRight1 — i.e. everything on the left of both partitions is smaller than everything on the right of both partitions.
- If maxLeft1 > minRight2, i is too big, so move the search left (high = i - 1).
- Otherwise (maxLeft2 > minRight1), i is too small, so move the search right (low = i + 1).
Once a valid partition is found: if m+n is odd, the median is max(maxLeft1, maxLeft2); if even, it's the average of max(maxLeft1, maxLeft2) and min(minRight1, minRight2).

Walkthrough with nums1 = [1, 2, 5, 8] (m=4), nums2 = [3, 4, 6, 7, 9] (n=5):

halfLen = floor((4+5+1)/2) = 5, binary search i between 0 and 4.

i=2 → j=3: maxLeft1=nums1[1]=2, minRight1=nums1[2]=5, maxLeft2=nums2[2]=6, minRight2=nums2[3]=7. Check fails since maxLeft2(6) > minRight1(5), so i must increase.
i=3 → j=2: maxLeft1=nums1[2]=5, minRight1=nums1[3]=8, maxLeft2=nums2[1]=4, minRight2=nums2[2]=6. Now maxLeft1(5) <= minRight2(6) and maxLeft2(4) <= minRight1(8) — valid partition!

Since m+n=9 is odd, median = max(5, 4) = 5. ✓.

Time complexity: O(log(min(m,n))).

Solution 2: Binary search for the k-th smallest element

The median is just the k-th smallest element of the combined array (or the average of the k-th and (k+1)-th for even total length), so the problem reduces to "find the k-th smallest element across two sorted arrays without merging them".

To find the k-th smallest starting at pointers i in nums1 and j in nums2:

If nums1 is exhausted (i >= m), the answer is nums2[j + k - 1]; symmetrically if nums2 is exhausted.
If k == 1, the answer is min(nums1[i], nums2[j]).
Otherwise compare mid1 = nums1[i + k/2 - 1] and mid2 = nums2[j + k/2 - 1] (treated as Infinity if the index is out of bounds).
- Whichever is smaller, the k/2 elements up to and including it can never be the k-th smallest overall (there are already at least k/2 elements from the other array that are also smaller than it, plus the ones before it in its own array) — so they can all be safely discarded.
- Recurse with that pointer advanced by k/2 and k reduced by k/2.

The median is then computed as the average of the floor((m+n+1)/2)-th and floor((m+n+2)/2)-th smallest elements (for odd total length these two indices coincide, so it naturally reduces to a single value).

Walkthrough with the same arrays, finding the 5th smallest (k=5, since m+n=9 is odd both calls use k=5):

f(i=0, j=0, k=5): mid1 = nums1[0+2-1] = nums1[1] = 2, mid2 = nums2[0+2-1] = nums2[1] = 4. mid1 < mid2, so discard nums1[0..1] → f(i=2, j=0, k=3).
f(i=2, j=0, k=3): mid1 = nums1[2+1-1] = nums1[2] = 5, mid2 = nums2[0+1-1] = nums2[0] = 3. mid2 < mid1, so discard nums2[0] → f(i=2, j=1, k=2).
f(i=2, j=1, k=2): mid1 = nums1[2+1-1] = nums1[2] = 5, mid2 = nums2[1+1-1] = nums2[1] = 4. mid2 < mid1, so discard nums2[1] → f(i=2, j=2, k=1).
f(i=2, j=2, k=1): k==1, return min(nums1[2], nums2[2]) = min(5, 6) = 5.

Median = 5. ✓.

Time complexity: O(log(m+n)), since k is roughly halved on each recursive call.

Implementation

Back to index

FilesExpand file tree

sort.md

Latest commit

History

sort.md

File metadata and controls

Sort

Insertion Sort

Description

Solution

Example

Performance

Notes

Implementation

Merge Sort

Description

Solution

Example

Performance

Notes

Implementation

Bubble Sort

Description

Solution

Example

Performance

Notes

Implementation

Selection Sort

Description

Solution

Example

Performance

Notes

Implementation

Counting Sort

Description

Solution

Example

Performance

Notes

Implementation

Quick Sort

Description

Solution

Example

Performance

Notes

Implementation

Median Of Two Sorted Arrays

Description

Example

Solution

Solution 1: Binary search on partition

Solution 2: Binary search for the k-th smallest element

Implementation