Efficient List Sorting in Python

Sorting lists is a fundamental operation in computer science, crucial for organizing data and enabling efficient searching and analysis. This challenge asks you to implement a sorting algorithm in Python to arrange elements within a list in ascending order. Understanding and implementing sorting algorithms is a cornerstone of algorithmic thinking and problem-solving.

Problem Description

You are tasked with creating a Python function called sort_list that takes a list of numbers as input and returns a new list containing the same numbers, but sorted in ascending order. The function should not modify the original list. You can choose any sorting algorithm you prefer (e.g., bubble sort, insertion sort, merge sort, quicksort). However, consider efficiency – while a simple algorithm is acceptable, strive for a reasonably performant solution, especially when dealing with larger lists.

Key Requirements:

• The function must accept a list of numbers (integers or floats) as input.
• The function must return a new sorted list. The original list must remain unchanged.
• The sorting should be in ascending order (smallest to largest).
• The function should handle lists containing duplicate numbers correctly.
• The function should handle empty lists gracefully.

Expected Behavior:

The function should correctly sort lists of varying lengths and containing different numerical values. It should also handle edge cases such as empty lists and lists with only one element.

Edge Cases to Consider:

• Empty list: []
• List with a single element: [5]
• List with duplicate elements: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
• List with negative numbers: [-2, 1, -5, 0, 3]
• List with floats: [1.5, 2.0, 0.75, 3.14]

Examples

Example 1:

Input: [3, 1, 4, 1, 5, 9, 2, 6]
Output: [1, 1, 2, 3, 4, 5, 6, 9]
Explanation: The input list is sorted in ascending order, with duplicate values preserved.

Example 2:

Input: []
Output: []
Explanation: An empty list remains an empty list after sorting.

Example 3:

Input: [5]
Output: [5]
Explanation: A list with a single element is already sorted.

Example 4:

Input: [-2, 1, -5, 0, 3]
Output: [-5, -2, 0, 1, 3]
Explanation: The list containing negative numbers is sorted correctly.

Constraints

• The input list will contain only numbers (integers or floats).
• The length of the input list can range from 0 to 10,000 elements.
• The function should have a time complexity of O(n log n) or better for efficient sorting, especially for larger lists. While O(n^2) solutions are acceptable for smaller lists, consider the performance implications for larger inputs.
• The function should not use any built-in Python sorting functions like sorted() or list.sort(). The goal is to implement a sorting algorithm yourself.

Notes

• Consider the trade-offs between different sorting algorithms in terms of time and space complexity.
• Think about how to handle edge cases gracefully to ensure the function behaves correctly in all scenarios.
• While you can choose any sorting algorithm, understanding the underlying principles of the algorithm you choose is important. Document your choice and briefly explain why you selected it.
• Focus on creating a clear, readable, and well-documented solution.