Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Sort an Array (Merge Sort vs Quicksort)

Sort an array without the built-in sort: merge sort in Python with a guaranteed O(n log n), how it compares with quicksort, tested code and a live race visual.

Also searched as: merge sort in python · implement sorting without built-in sort · merge sort vs quicksort interview

🏁

Try it live Free

Sorting Race: Insertion vs Merge vs Quick

Race insertion, merge and quick sort on the same array and flip the input. You will see merge sort stay steady while naive-pivot quicksort collapses on sorted data and insertion sort wins on nearly sorted data.

Also useful: Quicksort, Partition & Conquer

Open the playground →

The problem

Sort a list of integers in ascending order without calling a built-in sort. The solution should run in O(n log n) time.

Inputnums = [5, 2, 3, 1]
Output[1, 2, 3, 5]
Inputnums = [5, 1, 1, 2, 0, 0]
Output[0, 0, 1, 1, 2, 5]

Duplicates are kept.

The key insight

Merge sort splits the list in half, sorts each half recursively, and merges two sorted halves by repeatedly taking the smaller front element. Splitting gives log n levels and each level does O(n) merging, so it is always O(n log n). Quicksort is often faster in practice but can hit O(n²) with a bad pivot.

Brute force first: Insertion or bubble sort is O(n²) and times out on large inputs.

Step-by-step approach

  1. If the list has 0 or 1 elements, it is already sorted; return it.
  2. Split it at the middle and recursively sort both halves.
  3. Merge: walk two pointers over the halves, appending the smaller element each time.
  4. Append whatever remains of either half.
  5. Use <= when comparing so equal elements keep their order (merge sort is stable).

Python solution

PYTHON 3tested
def sort_array(nums):
    if len(nums) <= 1:
        return list(nums)
    mid = len(nums) // 2
    left = sort_array(nums[:mid])
    right = sort_array(nums[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:    # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Complexity

TimeO(n log n)
SpaceO(n)

The list is halved log n times and each level merges n elements in total. The merge needs O(n) temporary space.

Common mistakes

Frequently asked questions

What is the time and space complexity of merge sort?

O(n log n) time in the best, average and worst case, and O(n) extra space for merging. Quicksort averages O(n log n) with O(log n) stack space but has an O(n²) worst case.

Merge sort or quicksort in an interview?

Merge sort is easier to get right and has a guaranteed bound. Quicksort with a random pivot is a good answer if you mention the worst case and how randomisation avoids it.

What sort does Python use?

Python's sorted and list.sort use Timsort, a stable hybrid of merge sort and insertion sort that is very fast on partly sorted data.

Is merge sort stable?

Yes, as long as the merge takes from the left half when elements are equal. Stability matters when sorting records by one key after another.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.