Basic example
Input
lomuto_quicksort([3, 6, 1, 5, 2])
Output
[1, 2, 3, 5, 6]
The input list is sorted into ascending order using Lomuto quicksort and the sorted list is returned.
Full lesson preview
Implement Lomuto quicksort
Implement quicksort using the Lomuto partition scheme to sort a list of integers in-place and return a new sorted list.
Python practice15 minSearching & SortingIntermediateLast updated March 25, 2026
Problem statement
Quicksort is an efficient divide-and-conquer sorting algorithm. Implement quicksort using the Lomuto partition scheme. Your function should accept a list of integers (which may contain duplicates and negative numbers) and return a new list sorted in non-decreasing order. Use the Lomuto partition approach where you pick the last element as the pivot and partition the array around it.
Task
Write a function that sorts a list of integers using the Lomuto partition quicksort algorithm and returns a sorted list.
Examples
Input format
A single list of integers, e.g. [3, 1, 2].
Output format
A list of integers sorted in non-decreasing order, e.g. [1, 2, 3].
Constraints
- Do not use built-in sort/sorted.
- Must use Lomuto partition scheme (choose last element as pivot).
- Expected average time complexity: O(n log n), worst-case O(n^2).
- You may return a new list or sort in-place and return it.
Samples
Sample 1
Input
[4, 2, 4, 3, 2, 1]
Output
[1, 2, 2, 3, 4, 4]
Duplicates are handled and appear in sorted order.