Sorts for Nearly-Sorted Data | Dataford Interview Questions

Merge sort vs bubble sort when data is nearly sorted.

Asked in the Technical stage. Implement an in-place sorting function for an integer array that is expected to be nearly sorted. Use bubble sort with an early-termination optimization, then explain its complexity and when merge sort would be a better choice.

Contract

sort_nearly_sorted(nums) receives a mutable list of integers and returns the same list after sorting it in ascending order.

Constraints

0 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
The function must sort nums in place
Duplicate values are allowed

Function Signature

def sort_nearly_sorted(nums):

Your question is Sorts for Nearly-Sorted Data. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem