lukeleeai
Published in

lukeleeai

Selection, Insertion, and Merge Sort

In this post, we’re going to explore a few basic sorting algorithms.

Selection Sort

This is the simplest and most naive approach to sort an array. As you iterate an array, you select the smallest among the remaining elements and swap them.

for (i=0; i<N; i++):
min = i
for (j=i+1; j<n; j++):
if arr[j] < arr[min]:
min = j
swap(i, min)

Time Complexity

Insertion Sort

for (i=1; i<N; i++):
for (j=i; i>=0; j--):
if (arr[j] < arr[j-1]):
swap(j, j-1)
else: // stop cuz it's already sorted
break

Time Complexity

In the best case,
It’s already sorted, so we don’t need to iterate backwards every iteration.
N-1 compares, 0 exchanges

In the worst case,
It’s sorted in reverse order.
N²/2 compares, N²/2 exchanges

On average,
N²/4 compares, N²/4 exchanges

Merge Sort

John Von Neumann suggested Merge Sort, which is based on Divide and Conquer paradigm. The key idea is to keep dividing the array into two, thus making it easier to sort them, and merging them into a complete sorted array.

Here’s a Python code below.

def mergeSort(array):
if len(array) > 1:
mid = len(array) // 2

I = array[:mid]
J = array[mid:]

mergeSort(I)
mergeSort(J)

i = k = j = 0

while i < len(I) or j < len(J):
if i == len(I):
array[k:k+len(J)-j] = J[j:len(J)]
break

if j == len(J):
array[k:k+len(I)-i] = I[i:len(I)]
break

if I[i] <= J[j]:
array[k] = I[i]
i += 1

else:
array[k] = J[j]
j += 1

k += 1

Time Complexity

It’s an optimal compare-based algorithm with its time complexity O(NlogN) being the lower bound. For memory, it uses an extra space proportional to N, though.

In-place & Stable

In-place

An algorithm is said to be in-place if it uses less than C log N extra memory. A selection and insertion algorithm is so.

Stable

An algorithm is stable if it preserves the order of records with equal keys.

In the example above, a stable algorithm produces the upper table in the far right. You can observe that the records are ordered by surname as well.

A merge sort and insertion sort are stable. If you think about it, you only swap two local elements in an insertion sort. In a merge sort, locally, you’re sorting two sorted arrays.

A selection sort is not stable. You can’t guarantee that it preserves the orders.

--

--

--

Hello, world.

Recommended from Medium

Bring your game to AAA status through Post Processing!

Bitcoin, Supersonic Flight and Christmas Lights

From logic and math to code. For dummies. Part III. Dependent types

Working with Arrays in Go(golang)

He Always Asks Why. Meet Andrzej — a Senior Android Developer

DevConf: sketchnotes and a workshop

Visual Studio Code: A Newbie’s Guide to Personalizing your Workspace and Why it Might Matter

A collage of screenshots that present different themes that a user can choose to customize and personalize their workspace as they write their programs.

The Magic Behind Service Workers

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
etherhyun

etherhyun

More from Medium

Leetcode Q263. Ugly Number (Q239)

Abstract Data Types and Data Structures

LeetCode — Spiral Matrix

Minimum Spanning Tree & Prim’s Algorithm