Sorintg refers to arranging data in a particualr format(order).

The importance of sorting lies in the fact that data seraching can be optimized to a very high level, if data is stored in a sorted manner. Followings are some of the examples of sorting in real-life scenarios:

  • Telephone Directory
  • Dictionary

Here, I need to mention sorting algorithms may require some extra space for comparison and temporary storage of few data elements. When it is happening in place, or for example, within the array itself. This is called in-place sorting.

The scenario is here and I provide as many solutions as I can. Source: Leetcode soring problem

Bubble Sort Algorithm

It is not suitable for large data sets as its average and worst case complexity are of O(n^2) where n is the number of items.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        L = len(nums)
        swap = True
        while swap:
            swap = False
            for i in range(L-1):
                if nums[i] > nums[i+1]:
                    nums[i],nums[i+1],swap = nums[i+1], nums[i], True
        return nums

Here, we use swap as the flag to decide should we continue the swapping process.

Insertion Sort

This is an in-place comparison-based sorting algorithm. The main is to compare with all elements in the sorted sub-list and insert the value into the right place.

class Solution:
    def sortArray(self, N: List[int]) -> List[int]:
        L = len(N)
        for i in range(1,L):
            for j in range(0,i):
                if N[i] < N[j]:
                    N.insert(j, N.pop(i))
                    break
        return N

These two methods exceed the time limit.

Selection Sort

This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts.

The idea is to pin the value on list and then the whole list is scanned sequentially. Imagine we have 14 in the first position, we would see if the rest array has a smaller value than 14.

This honestly would be my first choice. I would set the MIN to location 0 and search the minimum element in the list and then swap. Last, increment MIN to point to next element.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        L = len(nums)
        result = []
        for i in range(L):
            result.append(nums.pop(min(range(L-i), key = lambda x: nums[x])))
        return result

Merge Sort

It is sorting technique based on divide and conquer. With worst-case time complexity being O(nlogn).

The logic ides would be divide the array into half and then half.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergesort(A):
            L = len(A)
            if L == 1: return A
            LH,RH = mergesort(A[:L//2]), mergesort(A[L//2:])
            return merge(LH,RH)
        def merge(LH,RH):
            LLH,LRH = len(LH),len(RH)
            s, i, j = [],0,0
            while i < LLH and j < LRH:
                if LH[i]<= RH[j]: i,_ = i + 1, s.append(LH[i])
                else: j,_ = j + 1, s.append(RH[j])
            return s + (RH[j:] if i == LLH else LH[i:])
        return mergesort(nums)