I’m working with TypeScript that follows functional programming principles, meaning I want to keep immutability and avoid mutating any of the input arrays.

I’m using bubble sort, and I have an issue where I need to return a new sorted array without modifying the original one.

However, my current implementation seems to be adding unnecessary overhead by adding a .slice() at the end to create a new array.

export default function bubbleSort<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number): ReadonlyArray<T> {
  // Helper function to swap elements in an array
  const swap = (arr: ReadonlyArray<T>, i: number, j: number): ReadonlyArray<T> => {
    const newArr = [...arr]
    ;[newArr[i], newArr[j]] = [newArr[j], newArr[i]]
    return newArr
  }

  // Function to perform one full pass of bubble sort, bubbling the largest element to the end
  const bubblePass = (arr: ReadonlyArray<T>, n: number): [ReadonlyArray<T>, boolean] => {
    // Slice the array to ignore already sorted elements
    return arr.slice(1, n).reduce(
      ([accArray, swapped], _, i) => {
        if (compare(accArray[i], accArray[i + 1]) > 0) {
          return [swap(accArray, i, i + 1), true] // Swap if necessary and mark as swapped
        }
        return [accArray, swapped]
      },
      [arr, false] as [ReadonlyArray<T>, boolean],
    )
  }

  // Recursive function to apply the bubble sort until no more swaps are needed
  const sort = (arr: ReadonlyArray<T>, n: number): ReadonlyArray<T> => {
    if (n <= 1) return arr // Base case: if the array length is 1 or less, return the array
    const [newArr, swapped] = bubblePass(arr, n)
    return swapped ? sort(newArr, n - 1) : newArr // Recur with the size reduced by 1 if swapped, else return sorted array
  }

  return sort([...array], array.length)
}

Then, the errors happen:

const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
const sorted = bubbleSort(arr, (a, b) => a - b)
sorted.push(123) // Property 'push' does not exist on type 'readonly number[]'.

It works with slice method at the end

export default function bubbleSort<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number): T[]  {
  // Helper function to swap elements in an array
  const swap = (arr: ReadonlyArray<T>, i: number, j: number): ReadonlyArray<T> => {
    const newArr = [...arr]
    ;[newArr[i], newArr[j]] = [newArr[j], newArr[i]]
    return newArr
  }

  // Function to perform one full pass of bubble sort, bubbling the largest element to the end
  const bubblePass = (arr: ReadonlyArray<T>, n: number): [ReadonlyArray<T>, boolean] => {
    // Slice the array to ignore already sorted elements
    return arr.slice(1, n).reduce(
      ([accArray, swapped], _, i) => {
        if (compare(accArray[i], accArray[i + 1]) > 0) {
          return [swap(accArray, i, i + 1), true] // Swap if necessary and mark as swapped
        }
        return [accArray, swapped]
      },
      [arr, false] as [ReadonlyArray<T>, boolean],
    )
  }

  // Recursive function to apply the bubble sort until no more swaps are needed
  const sort = (arr: ReadonlyArray<T>, n: number): ReadonlyArray<T> => {
    if (n <= 1) return arr // Base case: if the array length is 1 or less, return the array
    const [newArr, swapped] = bubblePass(arr, n)
    return swapped ? sort(newArr, n - 1) : newArr // Recur with the size reduced by 1 if swapped, else return sorted array
  }

  return sort([...array], array.length).slice()
}

The Issue: The .slice() at the end solves the immutability issue, but it seems to be a waste of performance, especially since the array has already been copied during the sorting process.