Sorting algorithms

[sophryu99]

Sorting algorithms Time & Space complexity

[sophryu99]

Merge sort

1. dividing an array into smaller subarrays
2. sorting each subarray
3. merging the sorted subarrays back together

Main advantage

• Time complexity of O(nlog(n)) -> very efficient
• Stable sort: the order of elements with equal values is preserved during the sort
• Good choice for large datasets as it is fast and easy to implement
• Easily used in conjunction with other sort algorithms

Drawbacks

• Slower for smaller tasks
• Requires an additional memory of space O(n) to store the subarrays that are used during the sorting process
• Does not exit even if the array is all sorted

Algorithm

step 1: start

step 2: declare array and left, right, mid variable

step 3: perform merge function.
    if left > right
        return
    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)
    merge(array, left, mid, right)

step 4: Stop

# Python program for implementation of MergeSort
def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

[sophryu99]

Insertion sort

• Similar to the way you sort playing cards in your hands

1. Array is virtually split into a sorted and an unsorted part
2. Values from the unsorted part are picked and placed at the correct position in the sorted part

Main advantages

• One of the simplest algorithms with simple implementation
• Efficient for small data values
• Appropriate for data sets which are already partially sorted

Drawbacks

• O(n^2) time complexity
• Not suitable for large dataset due to its inefficiency

Algorithm

Iterate from arr[1] to arr[N] over the array. 

Compare the current element (key) to its predecessor. 

If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

# Python program for implementation of Insertion Sort

# Function to do insertion sort
def insertionSort(arr):

	# Traverse through 1 to len(arr)
	for i in range(1, len(arr)):

		key = arr[i]

		# Move elements of arr[0..i-1], that are
		# greater than key, to one position ahead
		# of their current position
		j = i-1
		while j >= 0 and key < arr[j] :
				arr[j + 1] = arr[j]
				j -= 1
		arr[j + 1] = key

Insertion sort